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

#define ll long long
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back



using namespace std;

const int MAXN = 2e5;
const ll inf = 1e18;
const int lg = 20;
int t = 1;
int n,m;

int tin[MAXN];
int tout[MAXN];
vector<vector<int>> graf(MAXN);
vector<int> dist(MAXN);
vector<vector<int>> up(lg, vector<int>(MAXN));

void fillUp()
{
    for(int i=1; i<lg; i++) for(int j=0; j<n; j++)up[i][j] = up[i-1][up[i-1][j]];
}

bool isAnc(int x, int y)
{
    return (tin[x]<=tin[y]) && (tout[x] >= tout[y]);
}

int lca(int x, int y)
{
    if(x == y)return x;
    if(isAnc(x,y))return x;
    if(isAnc(y,x))return y;

    for(int i = lg-1; i>=0; i--)if(!isAnc(up[i][x],y))x = up[i][x];
    return up[0][x];

}


void dfs(int nod, int p, int d)
{
    tin[nod] = t++;
    dist[nod] = d;
    up[0][nod] = p;
    for(auto x: graf[nod])if(x!=p)dfs(x, nod, d+1);
    tout[nod] = t++;
}

int calcDist(int x, int y)
{
    return dist[x] + dist[y] - 2*dist[lca(x,y)]+1;
}


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 = (int)R.size()+1;
    m = (int)D.size();
    for(auto x: R)
    {
        graf[x.fi].pb(x.sc);
        graf[x.sc].pb(x.fi);
    }
    dfs(0,0,1);
    fillUp();
    bool case4 = true;
    for(int i=0; i<m; i++)if(D[i]!= 1ll*1e6*i)case4 = false;
    vector<int> rez(m);
    if(case4)
    {
        for(int i=0; i<m; i++)
        {
            if(I[i] == 0)rez[i] = 0;
            else rez[i] = calcDist(S[i], T[i]);
        }
    }
    return rez;
}
