#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;

const int MAXN=150009,LOG=19,INF=1000000009;
int dub[MAXN],in[MAXN],out[MAXN];
vector<int> graf[MAXN];
int timer=0;
void dfs(int node,int tr,int pr){
    dub[node]=tr;
    in[node]=++timer;
    for(auto x:graf[node]){
        if(x==pr) continue;
        dfs(x,tr+1,node);
    }
    out[node]=++timer;
}
int anc[MAXN][LOG];

int lca(int a,int b){
    if(a==b) return a;
    if(in[a]<in[b]&&out[a]>out[b]) return a;
    if(in[b]<in[a]&&out[b]>out[a]) return b;
    int node=a;
    for(int i=LOG-1; i>=0; i--){
        int p=anc[node][i];
        if(in[p]<in[b]&&out[p]>out[b]) continue;
        node=p;
    }
    return anc[node][0];
}



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
) {
    int n=R.size(),m=S.size();
    for(auto x:R){
        int a=x.first,b=x.second;
        graf[a].push_back(b);graf[b].push_back(a);
    }
    dfs(0,0,-1);
    in[MAXN-1]=-1;out[MAXN-1]=INF;
    for(int i=0; i<MAXN; i++){
        for(int j=0; j<LOG; j++)
            anc[i][j]=MAXN-1;
    }
    for(int i=0; i<n; i++){
        for(auto x:graf[i]){
            if(dub[x]<dub[i])
                anc[i][0]=x;
        }
    }
    for(int i=1; i<LOG; i++){
        for(int node=0; node<n; node++){
            anc[node][i]=anc[anc[node][i-1]][i-1];
        }
    }
    vector<int> rez(m);
    for(int i=0; i<m; i++){
        if(I[i]){
            int c=lca(S[i],T[i]);
            //cout << c << "!" << endl;
            rez[i]=dub[S[i]]+dub[T[i]]-2*dub[c];
        }
        else
            rez[i]=0;
    }
    return rez;
}
/*
7 2
0 1
1 2
1 3
2 4
2 5
3 6
0 4 6 1
100 2 0 0

ocekivano:
4
0
*/
