#include "infection.h"
#include <bits/stdc++.h>
#include <utility>
using namespace std;
const int N=5001, LOG=13;
int up[N][LOG], depth[N];
vector<int> adj[N];
bool b[N];

void dfs(int u){
    for(auto it : adj[u]){
        if(it!=up[u][0]){
            depth[it]=depth[u]+1;
            up[it][0]=u;
            for(int i=1; i<LOG; i++){
                up[it][i]=up[ up[it][i-1] ][i-1];
            }
            dfs(it);
        }
    }
}


int LCA(int u, int v){
    if (u==v) {
        return u;
    }
    if(depth[u]<depth[v]){
        swap(u, v);
    }
    for(int i=LOG; i>=0; i--){
        if(depth[up[u][i]]>=depth[v]){
            u=up[u][i];
        }
    }
    if (u==v) {
        return u;
    }
    for(int i=LOG-1; i>=0; i--){
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}



vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
) {

    for (auto it : R) {
        adj[it.first].push_back(it.second);
        adj[it.second].push_back(it.first);
    }

    int m=T.size();
    up[0][0]=0;
    depth[0]=0;
    dfs(0);
    vector<int> ans1;

    for(int i=0;i<m;i++){
        ans1.push_back(0);
    }
    vector<int> v[m+1];
    for(int i=0;i<m;i++) {
        int x=LCA(S[i], T[i]);
        if(x==S[i] && x!=T[i]){
            int u=T[i];
            while(u!=x){
                v[i].push_back(u);
                u=up[u][0];
            }
            v[i].push_back(x);
            reverse(v[i].begin(), v[i].end());
        }else if(x==T[i] && x!=S[i]){
            int u=S[i];
            while(u!=x){
                v[i].push_back(u);
                u=up[u][0];
            }
            v[i].push_back(x);
        }else if(x==S[i] && x==T[i]){ v[i].push_back(x); }
        else{
            int u=S[i];
            while(u!=x){
                v[i].push_back(u);
                u=up[u][0];
            }
            v[i].push_back(x);
            vector<int> w;
            w.clear();
            u=T[i];
            while(u!=x){
                w.push_back(u);
                u=up[u][0];
            }
            reverse(w.begin(), w.end());
            for(auto it : w){
                v[i].push_back(it);
            }
        }
    }
    int j=0;
    bool bl=true;
    while(bl){
        bl=false;
        for(int i=0; i<m; i++){
            if(v[i].size()>j){
                bl=true;
                if(I[i]==true) b[v[i][j]]=true;
            }
        }
        for(int i=0; i<m; i++){
            if(v[i].size()>j){
                if(b[v[i][j]]==true){
                    ans1[i]++;
                    I[i]=true;
                }
            }
        }
        j++;
    }
    return ans1;
}