#include "infection.h"
#include<bits/stdc++.h>
using namespace std;
struct cell
{
    int s,a,b,c,ind;
};
bool cmp(cell a1,cell a2)
{
    return a1.s<a2.s;
}
int n,m,br,tim,to,in[200005],inf[200005],last[200005];
cell a[200005];
vector<int>v[200005],h,p[200005],cur[200005],ne[200005],otg;
void path(int beg,int par,int fin,int o)
{
    h.push_back(beg);
    if(beg==fin)
    {
        p[o]=h;
        h.pop_back();
        return;
    }
    int w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w!=par)
        {
            path(w,beg,fin,o);
        }
    }
    h.pop_back();
}
void infect(int beg,int par)
{
    int w,b=0;
    for(int i=0;i<cur[beg].size();i++)
    {
        if(inf[cur[beg][i]])
        {
            b=1;
            break;
        }
    }
    if(b)
    {
        for(int i=0;i<cur[beg].size();i++)
        {
            if(!inf[cur[beg][i]])
            {
                inf[cur[beg][i]]=tim+1;
            }
        }
    }
    for(int i=0;i<cur[beg].size();i++)
    {
        w=cur[beg][i];
        in[w]++;
        if(in[w]>=p[w].size())
        {
            last[w]=tim+2;
            br--;
        }
        else
        {
            ne[p[w][in[w]]].push_back(w);
        }
    }
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w!=par)
        {
            infect(w,beg);
        }
    }
}
void sim()
{
    while(br||to!=m+1)
    {
        if(!br)tim=a[to].s;
        while(to<=m&&a[to].s==tim)
        {
            cur[a[to].a].push_back(to);
            br++;
            to++;
        }
        //infect(0,-1);
        for(int i=0;i<=n;i++)
        {
            cur[i]=ne[i];
            ne[i].clear();
        }
        tim++;
    }
}
vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I)
{
    for(int i=0;i<R.size();i++)
    {
        v[R[i].first].push_back(R[i].second);
        v[R[i].second].push_back(R[i].first);
        n=max(R[i].first,R[i].second);
    }
    m=D.size();
    for(int i=1;i<=m;i++)
    {
        a[i].s=D[i-1];
        a[i].a=S[i-1];
        a[i].b=T[i-1];
        a[i].c=I[i-1];
        a[i].ind=i;
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        path(a[i].a,-1,a[i].b,i);
        otg.push_back(0);
        if(a[i].c)inf[i]=a[i].s+1;
    }
    to=1;
    sim();
    for(int i=1;i<=m;i++)
    {
        if(inf[i])otg[a[i].ind-1]=last[i]-inf[i];
    }
    return otg;
}
