#include "infection.h"
#include<bits/stdc++.h>
#define MAXLOG 19
#define MAXN 150003
using namespace std;
int bl[150007][23],dep[150007];
int p[1500007];
int lift(int x,int k)
{
    if(x==0)
    {
        return 0;
    }
    if(k==0)
    {
        return p[x];
    }
    if(bl[x][k]!=-1)
    {
        return bl[x][k];
    }
    bl[x][k]=lift(lift(x,k-1),k-1);
    return bl[x][k];
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    for(int i=MAXLOG-1;i>=0;i--)
    {
        if(dep[lift(x,i)]>=dep[y])
        {
            x=lift(x,i);
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=MAXLOG-1;i>=0;i--)
    {
        if(lift(x,i)!=lift(y,i))
        {
            x=lift(x,i);
            y=lift(y,i);
        }
    }
    return p[x];
}
int dist(int x,int y)
{
    int lca=LCA(x,y);
    return (dep[x]+dep[y]-2*dep[lca]);
}
vector<int>edges[150007];
int cnt=0;
void dfs(int x,int pp)
{
    p[x]=pp;
    cnt++;
    dep[x]=dep[pp]+1;
    for(auto el:edges[x])
    {
        if(el==pp)
        {
            continue;
        }
        dfs(el,x);
    }
}
int tim[MAXN];
bool iinf[MAXN];
unordered_set<int>lft;
unordered_set<int>curr[5007];
std::vector<int> solve(std::vector<std::pair<int, int>> ed,std::vector<long long> d,std::vector<int> s,std::vector<int> t,std::vector<bool> inf) {
    vector<pair<long long,int> >v;
    for(int i=0;i<d.size();i++)
    {
        tim[i]=0;
        v.push_back({d[i],i});
        lft.insert(i);
        curr[s[i]].insert(i);
        if(inf[i])
        {
            iinf[s[i]]=1;
        }
    }
    for(auto [x,y]:ed)
    {
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    p[0]=0;
    dep[0]=0;
    dfs(0,0);
    for(int i=0;i<MAXN;i++)
    {
        for(int j=0;j<MAXLOG;j++)
        {
            bl[i][j]=-1;
        }
    }
    while(lft.size())
    {
        for(int i=0;i<cnt;i++)
        {
            if(iinf[i])
            {
                for(auto el:curr[i])
                {
                    inf[el]=1;
                }
                iinf[i]=0;
            }
            curr[i].clear();
        }
        for(auto el:lft)
        {
            if(inf[el])
            {
                tim[el]++;
            }
        }
        for(int i=0;i<d.size();i++)
        {
            if(s[i]==t[i] && lft.find(i)!=lft.end())
            {
                lft.erase(i);
            }
        }
        if(lft.empty())
        {
            break;
        }
        for(auto el:lft)
        {
            int md=1e9;
            int mi=0;
            for(auto to:edges[s[el]])
            {
                if(dist(to,t[el])<md)
                {
                    md=dist(to,t[el]);
                    mi=to;
                }
            }
            s[el]=mi;
            curr[mi].insert(el);
            if(inf[el])
            {
                iinf[mi]=1;
            }
        }
    }
    vector<int>ans;
    for(int i=0;i<d.size();i++)
    {
        ans.push_back(tim[i]);
    }
    return ans;
}
