//chockolateman

#include<bits/stdc++.h>
#include "infection.h"

using namespace std;

int N,tin[150005],tout[150005],depth[150005],par[150005],jump[150005],timer;
vector<int> adj[150005];

void dfs1(int v,int p)
{
    depth[v] = depth[p] + 1;
    tin[v] = ++timer;
    par[v] = p;
    if(depth[jump[p]] - depth[jump[jump[p]]] == depth[p] - depth[jump[p]])
        jump[v] = jump[p];
    else
        jump[v] = p;
    for(auto u : adj[v])
        if(u != p)
            dfs1(u,v);
    tout[v] = timer;
}

bool is_ancesstor(int a,int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int LCA(int a,int b)
{
    while(!is_ancesstor(a,b))
    {
        if(!is_ancesstor(jump[a],b))
            a = jump[a];
        else
            a = par[a];
    }
    return a;
}

int dist(int a,int b)
{
    int lca = LCA(a,b);
    return depth[a] - depth[lca] + depth[b] - depth[lca];
}

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) {
    N = R.size();
    for(int i = 0 ; i < N ; i++)
    {
        R[i].first++;
        R[i].second++;
        adj[R[i].first].push_back(R[i].second);
        adj[R[i].second].push_back(R[i].first);
    }
    jump[1] = 1;
    dfs1(1,1);
    int M = D.size();
    for(int i = 0 ; i < M ; i++)
    {
        S[i]++;
        T[i]++;
    }
    vector<int> ret;
    for(int i = 0 ; i < M ; i++)
    {
        if(I[i])
            ret.push_back(dist(S[i],T[i])+1);
        else
            ret.push_back(0);
    }
    return ret;
}