#include <bits/stdc++.h>
#include "infection.h"
using namespace std;
vector<int>d,et,en,p;
vector<vector<int>>g;
vector<vector<int>>lca;
int timer=0;
void dfs(int a,int b)
{
    et[a]=timer;
    p[a]=b;
    timer++;
    lca[a][0]=b;
    d[a]=d[b]+1;
    for(int i=1;i<20;i++)
    {
        lca[a][i]=lca[lca[a][i-1]][i-1];
    }
    for(auto i:g[a])
    {
        if(i!=b)
        {
            dfs(i,a);
        }
    }
    en[a]=timer-1;
}
int findlca(int a,int b)
{
    if(d[a]<d[b])swap(a,b);
    for(int i=19;i>=0;i--)
    {
        if(d[lca[a][i]]>=d[b])a=lca[a][i];
    }
    if(a==b)return a;
    for(int i=19;i>=0;i--)
    {
        if(lca[a][i]!=lca[b][i])
        {
            a=lca[a][i];
            b=lca[b][i];
        }
    }
    return lca[a][0];
}
bool unatre(int a,int b)
{
    return et[a]<=et[b]&&en[b]<=en[a];
}
vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I)
{
    int n=R.size(),m=S.size();
    vector<int>res(m),sega=S;
    vector<bool>finish(m),bolni(n+1);
    d.resize(n+1);
    p.resize(n+1);
    g.resize(n+1);
    et.resize(n+1);
    en.resize(n+1);
    lca.resize(n+1,vector<int>(20));
    for(int i=0;i<n;i++)
    {
        g[R[i].first].push_back(R[i].second);
        g[R[i].second].push_back(R[i].first);
    }
    dfs(0,0);
    for(int i=0;i<m;i++)
    {
        if(I[i])bolni[sega[i]]=true;
    }
    for(int i=0;i<m;i++)
    {
        if(finish[i])continue;
        if(bolni[sega[i]])I[i]=1;
        if(I[i])res[i]++;
        if(sega[i]==T[i])finish[i]=true;
    }
    for(int i=0;i<n+1;i++)
    {
        bolni[i]=false;
    }
    for(int j=0;j<=n+1;j++)
    {
        for(int i=0;i<m;i++)
        {
            if(finish[i])continue;
            if(!unatre(sega[i],T[i]))sega[i]=p[sega[i]];
            else
            {
                for(auto z:g[sega[i]])
                {
                    if(z!=p[sega[i]]&&unatre(z,T[i]))
                    {
                        sega[i]=z;
                        break;
                    }
                }
            }
            if(I[i])bolni[sega[i]]=true;
        }
        for(int i=0;i<m;i++)
        {
            if(finish[i])continue;
            if(bolni[sega[i]])I[i]=1;
            if(I[i])res[i]++;
            if(sega[i]==T[i])finish[i]=true;
        }
        for(int i=0;i<n+1;i++)
        {
            bolni[i]=false;
        }
    }
    return res;
}
