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

using namespace std;

const long long MAXN=150000;
const long long LOG=24;

long long lift[MAXN+10][LOG];
long long par[MAXN+10];
long long dept[MAXN+10];

long long in[MAXN+10];
long long out[MAXN+10];
long long tim=0;
vector<long long>tree[MAXN+10];

void dfs(long long x, long long p)
{
    tim++;
    in[x]=tim;
    for (auto next:tree[x])
    {
        if (p==next) continue;
        dept[next]=dept[x]+1;
        par[next]=x;
        dfs(next, x);
    }
    tim++;
    out[x]=tim;
}

vector<int> solve(
vector<std::pair<int, int>> R,
vector<long long> D,
vector<int> S,
vector<int> T,
vector<bool> I
)
{
    long long n=0;
    for (long long i=0; i<R.size(); i++)
    {
        tree[R[i].first+1].push_back(R[i].second+1);
        tree[R[i].second+1].push_back(R[i].first+1);
        n=max(n, R[i].second+1LL);
        n=max(n, R[i].first+1LL);
    }
    out[0]=1e9;
    dept[1]=1;
    dfs(1, 0);

    for (long long i=1; i<=n; i++)
    {
        lift[i][0]=par[i];
    }

    for (long long log=1; log<LOG-1; log++)
    {
        for (long long i=1; i<=n; i++)
        {
            lift[i][log]=lift[lift[i][log-1]][log-1];
        }
    }
    vector<int>ret;
    for (long long i=0; i<S.size(); i++)
    {
        long long x=S[i]+1;
        long long y=T[i]+1;
        if (I[i]==0)
        {
            ret.push_back(0);
            continue;
        }

        if (in[x]<=in[y] && out[y]<=out[x]) {ret.push_back(dept[x]-dept[y]+1); continue;}
        if (in[y]<=in[x] && out[x]<=out[y]) {ret.push_back(dept[y]-dept[x]+1); continue;}
        long long lca=x;
        for (long long log=22; log>=0; log--)
        {
            long long next=lift[lca][log];
            if (in[next]<=in[y] && out[y]<=out[next]) continue;
            lca=next;
        }
        lca=par[lca];
        ret.push_back((dept[lca]-dept[x]+1)+(dept[lca]-dept[y]+1)-1);
    }

    return ret;
}


