#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;

const int MAXN=150009,LOG=19,INF=1000000009;
int dub[MAXN],in[MAXN],out[MAXN];
vector<int> graf[MAXN];
int timer=0;
void dfs(int node,int tr,int pr){
    dub[node]=tr;
    in[node]=++timer;
    for(auto x:graf[node]){
        if(x==pr) continue;
        dfs(x,tr+1,node);
    }
    out[node]=++timer;
}
int anc[MAXN][LOG];

int lca(int a,int b){
    if(a==b) return a;
    if(in[a]<in[b]&&out[a]>out[b]) return a;
    if(in[b]<in[a]&&out[b]>out[a]) return b;
    int node=a;
    for(int i=LOG-1; i>=0; i--){
        int p=anc[node][i];
        if(in[p]<in[b]&&out[p]>out[b]||p==MAXN-1) continue;
        node=p;
    }
    return anc[node][0];
}

bool bolestan[MAXN];
int dist[5009][5009];




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
) {
    int n=R.size(),m=S.size();n++;
    for(auto x:R){
        int a=x.first,b=x.second;
        graf[a].push_back(b);graf[b].push_back(a);
    }
    dfs(0,0,-1);
    in[MAXN-1]=-1;out[MAXN-1]=INF;
    for(int i=0; i<MAXN; i++){
        for(int j=0; j<LOG; j++)
            anc[i][j]=MAXN-1;
    }
    for(int i=0; i<n; i++){
        for(auto x:graf[i]){
            if(dub[x]<dub[i])
                anc[i][0]=x;
        }
    }
    for(int i=1; i<LOG; i++){
        for(int node=0; node<n; node++){
            anc[node][i]=anc[anc[node][i-1]][i-1];
        }
    }
    vector<int> rez(m,0);
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++)
            dist[i][j]=dub[i]+dub[j]-2*dub[lca(i,j)]+1;
    }
    vector<pair<int,int>> tr_stanje(m);
    vector<int> zarazen(n,0),finish(m,0);
    for(int i=0; i<m; i++){
        tr_stanje[i]={S[i],I[i]};
        if(I[i])
            zarazen[S[i]]=1;
        if(T[i]==S[i]) finish[i]=1;
    }
    for(int i=0; i<m; i++){
        if(zarazen[tr_stanje[i].first]){
            rez[i]++;
            tr_stanje[i].second=1;
        }
    }
    //int cnt=0;
    while(1){
        //cout << cnt++ << ":" << endl;
        for(int i=0; i<m; i++){//trazenje sledece pozicije radi
            if(finish[i]) continue;
            int tr=tr_stanje[i].first;
            int nxt=tr;
            for(auto x:graf[tr]){
                if(dist[tr][T[i]]>dist[x][T[i]])
                    nxt=x;
            }
            tr_stanje[i]={nxt,tr_stanje[i].second};
        }
        //cout << tr_stanje[1].first << "!"<< endl << endl;
        for(int i=0; i<n; i++) zarazen[i]=0;
        for(int i=0; i<m; i++){
            if(tr_stanje[i].second&&!finish[i])
                zarazen[tr_stanje[i].first]=1;
        }
        for(int i=0; i<m; i++){
            if(zarazen[tr_stanje[i].first]&&!finish[i]){
                rez[i]++;
                tr_stanje[i].second=1;
            }
        }
        for(int i=0; i<m; i++){
            if(tr_stanje[i].first==T[i])
                finish[i]=1;
        }
        int cnt=0;
        for(auto x:finish)
            cnt+=x;
        if(cnt==m) break;
    }

    return rez;
}
/*
7 2
0 1
1 2
1 3
2 4
2 5
3 6
0 4 6 1
100 6 6 1

ocekivano:
4
0

14 2
0 9
0 6
9 8
8 1
9 13
13 2
13 7
7 3
3 10
6 12
6 4
4 5
4 11
0 1 3 1
100 2 5 1


*/
