#include "infection.h"
#include <vector>
#include <utility>
#include<set>
#include<iostream>
using namespace std;
vector<int> adj[5001];
int n,m,p[5001],dep[5001],w[5001],koren;vector<int> ans;
bool stignal[5001],vis[5001];
void dfs(int st){
    vis[st]=true;
    for(int v:adj[st]){
        if(!vis[v]) {
            p[v]=st;
            dep[v]=dep[st]+1;
            dfs(v);
        }
    }
}
int lca[5001][5001];
int Lca(int u,int v){
    if(u>v) swap(u,v);
    if(p[u]==-1)return u;
    if(u==v) return lca[u][v]=v;
    if(lca[u][v]!=-1) return lca[u][v];
    if(dep[u]>dep[v]){
        return lca[u][v]=Lca(p[u],v);
    }
    else if(dep[u]<dep[v]){
        return lca[u][v]=Lca(u,p[v]);
    }
    else return lca[u][v]=Lca(p[u],p[v]);
}
int findnext(int v,int dest){
   // cout<<v<<" "<<dest<<" lca:"<<Lca(v,dest)<<endl;
    if(dep[Lca(v,dest)]<dep[v]) return p[v];
    else if(Lca(v,dest)==v) {
        for(int u:adj[v]){
            if(dep[u]>dep[v]){
               //     cout<<u<<" "<<dest<<" lca:"<<Lca(u,dest)<<endl;
                if(Lca(u,dest)==u) return u;
            }
        }
    }
    else return 5/0;
}
//set<pair<int,int>> hora;
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> l
) {//d - 0 s - start t- last i-zarazen?
    n=R.size()+1;m=s.size();//n-vurhove m-hora

    for(int i=0;i<n-1;i++){
        adj[R[i].second].emplace_back(R[i].first);
        adj[R[i].first].emplace_back(R[i].second);
        w[R[i].second]++;w[R[i].first]++;
        for(int ii=0;ii<n;ii++)lca[i][ii]=-1;
    }
    for(int ii=0;ii<n;ii++)lca[n-1][ii]=-1;
    for(int i=0;i<n;i++){if(w[i]==1){koren=i;break;}}
    long long maksd=0;
    for(int i=0;i<m;i++){
        maksd=max(maksd,d[i]);
        ans.emplace_back(0);
    }
    maksd+=n;
    dep[koren]=0;
    dfs(koren);
    p[koren]=-1;
 //   for(int i=0;i<n;i++){ cout<<dep[i]<<" "<<p[i]<<endl;}
    for(long long moment=0;moment<=maksd;moment++){
        bool zaraza[n];
        for(int ii=0;ii<n;ii++) zaraza[ii]=false;
        vector<int> cur;

        for(int p=0;p<m;p++){//putnik
            //if(t[p]==moment)
            if(!stignal[p] && moment>=d[p]){
                if(l[p]) zaraza[s[p]]=true;
                if(s[p]==t[p]){stignal[p]=true;}
                cur.emplace_back(p);
            }
        }
        for(int p:cur){//putnik
          //      cout<<"putik:"<<p<<" poz:"<<s[p]<<endl;
            if(zaraza[s[p]]){l[p]=true;ans[p]++;}
            if(s[p]!=t[p])s[p]=findnext(s[p],t[p]);
        }
    }
    return ans;
}
/*6 3
0 1
0 2
1 4
1 3
4 5
0 2 5 0
0 1 3 1
0 4 3 1*/
