#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 151000;
vector<int> path[MAXN];
vector<int> v[MAXN];
vector<int> ans;
bool infect[MAXN];
bool fl = false;
void DFS(int node, int par, int start, int endd, int idx){
    //cout << "Node: " << node << endl;
    if(node == endd){
        //cout << "Add " << node << endl;
        fl = true;
        path[idx].push_back(node);
        return;
    }
    for(int el: v[node]){
        if(el == par) continue;
        if(fl == true) continue;
        DFS(el, node, start, endd, idx);
        //cout << "Return after: " << node << endl;
    }
    //cout << "OUT" << endl;
    if(fl == true){
        //cout << "Add " << node << endl;
        path[idx].push_back(node);
        return;
    }
}
vector<int> solve(vector<pair<int, int>> r, vector<long long> d,
                  vector<int> s, vector<int> t, vector<bool> I){
    int n = 0, m = s.size();
    ans.resize(m);
    for(auto [a, b]: r){
        v[a].push_back(b);
        v[b].push_back(a);
        n = max(n, a);
        n = max(n, b);
    }
    n++;
    for(int i = 0; i < m; i++){
        //cout << "Find for: " << s[i] << ' ' << t[i] << endl;
        fl = false;
        DFS(s[i], 0, s[i], t[i], i);
        reverse(path[i].begin(), path[i].end());
        //for(int el: path[i]) cout << el << ' ';
        //cout << endl;
    }
    //cout << "After DFS" << endl;
    for(int i = 0; i < n; i++){
        //cout << "Day: " << i << endl;
        for(int person = 0; person < m; person++){
            //cout << "Person: " << person << endl;
            if(path[person].size() > i){
                int curr = path[person][i];
                //cout << "For person: " << person << ' ' << curr << endl;
                if(I[person] == true){
                    infect[curr] = true;
                    //cout << "Infect: " << curr << endl;
                }
            }
        }
        //cout << "Middle" << endl;
        for(int person = 0; person < m; person++){
            if(path[person].size() > i){
                int curr = path[person][i];
                if(infect[curr] == true) I[person] = true;
            }
            if(path[person].size() > i && I[person] == true){
                ans[person]++;
            }
        }
        //cout << "end of the day" << endl;
        for(int c = 0; c <= n; c++) infect[c] = false;
    }
    //cout << "Out" << endl;
    return ans;
}

