#include "infection.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=150050,lg=18;
vector<int>E[N];
int par[N][lg+1],depth[N];
void DFS(int u,int p=0){
    par[u][0]=p;
    depth[u]=depth[p]+1;
    for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u])if(i!=p)DFS(i,u);
}
int LCA(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}
int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
vector<int>solve(vector<pair<int,int>>R,vector<long long>D,vector<int>S,vector<int>T,vector<bool>I){
    for(auto &[u,v]:R)u++,v++;
    for(auto &i:S)i++;
    for(auto &i:T)i++;
    for(auto [u,v]:R){
        E[u].pb(v);
        E[v].pb(u);
    }
    DFS(1);
    int m=S.size();
    vector<int>res;
    for(int i=0;i<m;i++){
        int u=S[i],v=T[i];
        if(I[i]==0)res.pb(0);
        else res.pb(Dist(u,v)+1);
    }
    return res;
}
