#include "infection.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn =1e6+10;
vector<int> starts[maxn];
vector<int> endss[maxn];
int n,q;
int bord[maxn];
vector<int> edges[maxn];
int depth[maxn];
int st[25][maxn];
int tin[maxn],tout[maxn];
int timer=0;
void dfs(int start,int parent)
{
    tin[start]=++timer;
    st[0][start]=parent;
    for(auto e:edges[start])
    {
        if(e==parent) continue;
        depth[e]=depth[start]+1;
        dfs(e,start);
    }
    tout[start]=++timer;
}
void compLCA()
{
    for(int j=1;j<25;j++)
    {
        for(int i=1;i<=n;i++)
        {
            st[j][i]=st[j-1][st[j-1][i]];
        }
    }
}
bool isanc(int u,int v)
{
    if(tin[u]<=tin[v] && tout[u]>=tout[v]) return true;
    return false;
}
int lca(int u,int v)
{
  //  printf("in lca %d %d\n",u,v);
    if(isanc(u,v)) return u;
    if(isanc(v,u)) return v;
    if(depth[u]>depth[v]) swap(u,v);
    for(int i=24;i>=0;i--)
    {
       // printf("current v is %d\n",v);
        if(!isanc(st[i][v],u)) v=st[i][v];
    }
 //   printf("out lca\n");
    return st[0][v];
}
std::vector<int> solve(
    std::vector<std::pair<int, int>> R,///rebra
    std::vector<long long> D,///nachalni dni
    std::vector<int> S,///nachalna poziciq
    std::vector<int> T,///krajna poziciq
    std::vector<bool> I///bolen/nebolen
)
{

    q=D.size();
    vector<int> mom(q,0);
    n=R.size()+1;
    for(int i=0;i<=q;i++) mom[i]=-1;
    for(int i=0;i<n-1;i++)
    {
        R[i].f++;
        R[i].s++;
        edges[R[i].f].push_back(R[i].s);
        edges[R[i].s].push_back(R[i].f);
    }
    for(int i=0;i<q;i++)
    {
        S[i]++;
        T[i]++;
    }
    dfs(1,1);
   // printf("3\n");
    compLCA();
   // printf("2\n");
    for(int i=0;i<q;i++)
    {
       // printf()
        mom[i]=depth[S[i]]+depth[T[i]]-2*depth[lca(S[i],T[i])]+1;
        if(!I[i]) mom[i]=0;
    }
    return mom;
}

