#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5009;
vector<int> ans;
int dist[MAXN],father[MAXN],di[MAXN];
map<pair<long long,int>,vector<int>> party;
int dp[MAXN][20];
vector<int> edg[MAXN];
int N,M;

int f(int n,int p)
{
    if(dp[n][p]!=-1)return dp[n][p];
    if(p==0)return dp[n][p]=father[n];
    return dp[n][p]=f(f(n,p-1),p-1);
}

int lca(int a,int b)
{
    if(dist[a]>dist[b])swap(a,b);

    for(int i=19; i>=0; i--)
    {
        if((dist[b]-dist[a])&(1LL<<i))b=f(b,i);
    }

    if(a==b)return a;

    for(int i=19; i>=0; i--)
    {
        if(f(a,i)!=f(b,i))
        {
            a=f(a,i);
            b=f(b,i);
        }
    }

    return father[a];
}

void calcD(int a,int b,int d,int ind)
{
    int c=lca(a,b);
    di[ind]=dist[a]+dist[b]-2*dist[c]+1;
    int t=0;
    while(a!=c)
    {
        party[{d+t,a}].push_back(ind);
        t++;
        a=father[a];
    }
    party[{d+t,a}].push_back(ind);
    t=0;
    while(b!=c)
    {
        party[{d+(di[ind]-t)-1,b}].push_back(ind);
        t++;
        b=father[b];
    }
}

void dfs(int start,int f,int d)
{
    dist[start]=d;
    father[start]=f;

    for(auto i:edg[start])
    {
        if(i!=f)dfs(i,start,d+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
)
{
    memset(dp,-1,sizeof(dp));
    N=R.size()+1;
    M=I.size();
    for(auto i:R)
    {
        edg[i.first].push_back(i.second);
        edg[i.second].push_back(i.first);
    }

    dfs(0,0,0);

    for(int i=0; i<M; i++)
    {
        calcD(S[i],T[i],D[i],i);
        if(I[i])ans.push_back(D[i]);
        else ans.push_back(-1);
    }

    for(auto i:party)
    {
        bool zar=0;
        for(auto g:i.second)zar=zar||(ans[g]!=-1);
        if(zar)
        {
            for(auto g:i.second)
            {
                if(ans[g]==-1)ans[g]=i.first.first;
            }
        }

    }

    for(int i=0; i<M; i++)
    {
        if(ans[i]==-1)ans[i]=0;
        else ans[i]=di[i]-ans[i]+D[i];
    }

    return ans;
}
