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

using namespace std;

#define dim 5005
int tin[dim],tout[dim],dp[dim][20],niv[dim],timer;
vector<int> v[dim];
void dfs(int nod,int p=-1)
{
    dp[nod][0]=p;
    tin[nod]=++timer;
    for(auto y:v[nod])
    {
        if(y==p)
            continue;
        niv[y]=niv[nod]+1;
        dfs(y,nod);
    }
    tout[nod]=timer;
}
int calc(int a,int b)
{
    if(niv[a]<niv[b])
        swap(a,b);
    long long k;
    for(k=19;k>=0;k--)
    {
        if(niv[a]-(1LL<<k)>=niv[b])
        {
            a=dp[a][k];
        }
    }
    if(a==b)
        return a;
    for(k=19;k>=0;k--)
    {
        if(dp[a][k]!=dp[b][k])
        {
            a=dp[a][k];
            b=dp[b][k];
        }
    }
    return dp[a][0];
}
bool stramos(int a,int b)
{
    if(tin[a]<=tin[b] && tout[a]>=tout[b])
        return true;
    return false;
}
int nx(int nod,int lca,int dest)
{
    if(stramos(nod,dest)==true)
    {
        for(auto x:v[nod])
        {
            if(x==dp[nod][0])
                continue;
            if(stramos(x,dest)==true)
                return x;
        }
    }
    return dp[nod][0];
}
vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
)
{
    vector<int> ans(D.size(),-1);
    vector<int> lca(D.size());
    vector<int> locatie(D.size());
    for(auto [x,y]:R)
    {
        v[x].push_back(y);
        v[y].push_back(x);
    }
    long long i,k,N,M,zi,j;
    N=R.size()+1;
    M=D.size();
    dfs(0);
    for(k=1;k<20;k++)
    {
        for(i=0;i<N;i++)
        {
            dp[i][k]=dp[dp[i][k-1]][k-1];
        }
    }
    for(i=0;i<M;i++)
    {
        lca[i]=calc(S[i],T[i]);
        //cout<<S[i]<<" "<<T[i]<<" lca: "<<lca[i]<<endl;
    }
    vector<bool> term(M+1,false);
    for(i=0;i<M;i++)
    {
        if(I[i]==true)
            ans[i]=0;
        locatie[i]=S[i];
    }
    for(zi=0;zi<=N+1;zi++)
    {
        //cerr<<zi<<endl;
        for(i=0;i<M;i++)
        {
            //cout<<i<<" : "<<locatie[i]<<endl;
            if(term[i]==true)
                continue;
            for(j=i+1;j<M;j++)
            {
                if(term[j]==true)
                    continue;
                if(I[i]!=I[j] && locatie[i]==locatie[j])
                {
                    if(I[i]==1)
                        ans[j]=zi;
                    else
                        ans[i]=zi;
                    I[i]=I[j]=1;
                }
            }
        }
        for(i=0;i<M;i++)
        {
            if(term[i]==true)
                continue;
            if(locatie[i]==T[i])
            {
                term[i]=true;
                if(ans[i]==-1)
                    ans[i]=zi+1;
                else
                    ans[i]=zi+1-ans[i];
            }
            else
            {
                locatie[i]=nx(locatie[i],lca[i],T[i]);
            }

        }
    }
    return ans;
}
/*
9 5
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
1 0 5 1
3 5 7 0
4 5 7 0
8 7 8 0
10 0 1 0
*/
