#include <bits/stdc++.h>

using namespace std;


vector<int> adj[5001];
int parent[5001];

void dfs(int i,int p)
{
    parent[i]=p;
    for(auto it : adj[i])
    {
        if(p!=it)
        dfs(it,i);
    }
}

vector<vector<int>> vec;


std::vector<int> solve(
std::vector<std::pair<int, int>> R,
std::vector<long long> D,
std::vector<int> S,
std::vector<int> T,
std::vector<bool> I
)
{
    for(auto it : R)
    {
        adj[it.first].push_back(it.second);
        adj[it.second].push_back(it.first);
    }
    dfs(0,0);

    for(int i=0;i<S.size();i++)
    {
        int br1=S[i],br2=T[i];
        bool arr[5001]={};
        int lca=-1;
        for(;;)
        {
            if(br1==0 && br2==0)
            {
                lca=0;
                break;
            }
            if(br1!=0 && arr[br1]==true)
            {
                lca=br1;
                break;
            }
            arr[br1]=true;

            if(br2!=0 && arr[br2]==true)
            {
                lca=br2;
                break;
            }
            arr[br2]=true;
            br1=parent[br1];
            br2=parent[br2];
        }
        br1=S[i],br2=T[i];
        vector<int> vec1,vec2;
        for(;br1!=lca;br1=parent[br1])
        {
            vec1.push_back(br1);
        }
        for(;;br2=parent[br2])
        {
            vec2.push_back(br2);
            if(br2==lca)
                break;
        }
        for(int i=vec2.size()-1;i>=0;i--)
            vec1.push_back(vec2[i]);

        vec.push_back(vec1);

    }
    bool inf[5001]={};
    int res[5001]={};

    for(int i=0;i<I.size();i++)
    {
        if(I[i]==1)
        {

            res[i]=vec[i].size();

            inf[i]=true;


        }
    }

    for(int i=0;i<=R.size()+1;i++)
    {

        bool arr[5001]={};
        for(int j=0;j<vec.size();j++)
        {
            if(i>=vec[j].size())
                continue;
            else
            {
                if(inf[j]==true)
                    arr[vec[j][i]]=true;
            }

        }
        for(int j=0;j<vec.size();j++)
        {
            if(i>=vec[j].size())
                continue;
            else
            {
                if(arr[vec[j][i]]==true && inf[j]==false)
                {

                    inf[j]=true;
                    res[j]=vec[j].size()-i;
                }
            }


        }
    }




    vector<int> ress;
    for(int i=0;i<T.size();i++)
    {
        ress.push_back(res[i]);
    }
    return ress;

}