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

using namespace std;

#define MAXN 150005
#define MAXM 20

int n,m;
vector<int> adj[MAXN];
long long d[MAXN];int s[MAXN],t[MAXN];bool state[MAXN];
int dist[MAXN],parent[MAXM][MAXN];
vector<int> path[MAXN];
vector<int> currentnodes;
set<int> curr;
vector<int> nodes[MAXN];
vector<long long> times;
long long startday[MAXN],endday[MAXN];
int answer[MAXN];
map<long long,vector<int>> dodaj,ukloni;

void dfs(int node,int pret,int depth)
{
    dist[node]=depth;parent[0][node]=pret;
    for (int sled:adj[node])
    {
        if (sled!=pret) dfs(sled,node,depth+1);
    }
}

void construct(int node1,int node2,int target)
{
    vector<int> path1,path2;
    while (dist[node1]>dist[node2]) {path1.push_back(node1);node1=parent[0][node1];}
    while (dist[node2]>dist[node1]) {path2.push_back(node2);node2=parent[0][node2];}
    if (node1==node2)
    {
        for (int node:path1) path[target].push_back(node);
        path[target].push_back(node1);reverse(path2.begin(),path2.end());
        for (int node:path2) path[target].push_back(node);
        return;
    }
    while (node1!=node2)
    {
        path1.push_back(node1);node1=parent[0][node1];
        path2.push_back(node2);node2=parent[0][node2];
    }
    for (int node:path1) path[target].push_back(node);
    path[target].push_back(node1);reverse(path2.begin(),path2.end());
    for (int node:path2) path[target].push_back(node);
}

int jump(int node,int k)
{
    for (int bit=MAXM-1;bit>=0;bit--)
    {
        if (k&(1<<bit)) node=parent[bit][node];
    }
    return node;
}

int lca(int node1,int node2)
{
    if (dist[node1]<dist[node2]) swap(node1,node2);
    node1=jump(node1,dist[node1]-dist[node2]);
    if (node1==node2) return node1;
    for (int i=MAXM-1;i>=0;i--)
    {
        if (parent[i][node1]!=parent[i][node2])
        {
            node1=parent[i][node1];
            node2=parent[i][node2];
        }
    }
    return parent[0][node1];
}

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
)
{
    ios_base::sync_with_stdio(false);ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    n=(int)R.size()+1;m=(int)D.size();
    for (int i=0;i<n-1;i++) {int u=R[i].first+1,v=R[i].second+1;adj[u].push_back(v);adj[v].push_back(u);}
    for (int i=1;i<=m;i++) {d[i]=D[i-1];s[i]=S[i-1]+1;t[i]=T[i-1]+1;state[i]=I[i-1];}
    bool dequalzero=true;
    for (int i=1;i<=m;i++)
    {
        if (d[i]!=0) {dequalzero=false;break;}
    }
    bool subtask4=true;
    for (int i=1;i<=m;i++)
    {
        if (d[i]!=(long long)1000000*(i-1)) {subtask4=false;break;}
    }
    dfs(1,0,0);
    for (int i=1;i<MAXM;i++)
    {
        for (int node=1;node<=n;node++) parent[i][node]=parent[i-1][parent[i-1][node]];
    }
    if (n<=5000 and m<=5000 and dequalzero)
    {
        for (int i=1;i<=m;i++) construct(s[i],t[i],i);
        for (int node=1;node<=m;node++)
        {
            if (state[node]) answer[node]=(int)path[node].size();
        }
        int day=0;for (int i=1;i<=m;i++) currentnodes.push_back(i);
        while ((int)currentnodes.size()!=0)
        {
            for (int node:currentnodes) nodes[path[node][day]].push_back(node);
            for (int city=1;city<=n;city++)
            {
                bool infected=false;
                for (int node:nodes[city])
                {
                    if (state[node]) infected=true;
                }
                if (!infected) continue;
                for (int node:nodes[city])
                {
                    if (!state[node]) {answer[node]=(int)path[node].size()-day;state[node]=true;}
                }
            }
            for (int city=1;city<=n;city++) nodes[city].clear();
            currentnodes.clear();day++;
            for (int i=1;i<=m;i++)
            {
                if ((int)path[i].size()>day) currentnodes.push_back(i);
            }
        }
        vector<int> vec;for (int i=1;i<=m;i++) vec.push_back(answer[i]);
        return vec;
    }
    if (n<=5000 and m<=5000 and !dequalzero)
    {
        for (int i=1;i<=m;i++) construct(s[i],t[i],i);
        for (int i=1;i<=m;i++)
        {
            startday[i]=d[i];endday[i]=d[i]+(int)path[i].size()-1;
            dodaj[startday[i]].push_back(i);ukloni[endday[i]].push_back(i);
            for (int j=0;j<(int)path[i].size();j++) times.push_back(d[i]+j);
        }
        sort(times.begin(),times.end());times.erase(unique(times.begin(),times.end()),times.end());
        for (int node=1;node<=m;node++)
        {
            if (state[node]) answer[node]=(int)path[node].size();
        }
        for (long long day:times)
        {
            if (dodaj.find(day)!=dodaj.end())
            {
                for (int node:dodaj[day]) curr.insert(node);
            }
            for (int node:curr) nodes[path[node][day-d[node]]].push_back(node);
            for (int city=1;city<=n;city++)
            {
                bool infected=false;
                for (int node:nodes[city])
                {
                    if (state[node]) infected=true;
                }
                if (!infected) continue;
                for (int node:nodes[city])
                {
                    if (!state[node]) {answer[node]=endday[node]-day+1;state[node]=true;}
                }
            }
            for (int city=1;city<=n;city++) nodes[city].clear();
            if (ukloni.find(day)!=ukloni.end())
            {
                for (int node:ukloni[day]) curr.erase(node);
            }
        }
        vector<int> vec;for (int i=1;i<=m;i++) vec.push_back(answer[i]);
        return vec;
    }
    if (subtask4)
    {
        vector<int> vec;
        for (int i=1;i<=m;i++)
        {
            if (state[i]==true) vec.push_back(dist[s[i]]+dist[t[i]]-2*dist[lca(s[i],t[i])]+1);
            else vec.push_back(0);
        }
        return vec;
    }
};
