#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<int>> v, ord;
vector<int> pa;
int go = 0, ind = 0;
void dfs(int x, int p){
    pa[x] = p;
    if (x == go){
        int cur = x;
        while (cur != -1){
            ord[ind].push_back(cur);
            cur = pa[cur];
        }
        reverse(ord[ind].begin(), ord[ind].end());
        return;
    }
    for (auto el : v[x]){
        if (el != p){
            dfs(el, x);
        }
    }
}
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() + 1, m = S.size();
    v.assign(n + 1, vector<int>()), ord.assign(m + 1, vector<int>()), pa.assign(n + 1, 0);
    for (auto el : R){
        v[el.first].push_back(el.second);
        v[el.second].push_back(el.first);
    }
    vector<vector<ll>> so;
    for (int i = 0; i < m; i++){
        go = T[i], ind = i;
        dfs(S[i], -1);
        so.push_back({D[i], i});
    }
    sort(so.begin(), so.end());
    reverse(so.begin(), so.end());
    vector<int> ans(m, 0), cur, ncur;
    ll nd = 0;
    //cout<<"here";
    vector<ll> no(n + 1, -1);
    while (!so.empty() || !cur.empty()){
        if (cur.empty()){
            nd = so.back()[0];
        }
        while (!so.empty() && so.back()[0] <= nd){
            cur.push_back(so.back()[1]);
            so.pop_back();
        }
        int inf = 0;
        for (auto el : cur){
            if (I[el] == 1) no[ord[el][nd - D[el]]] = nd;
        }
        for (auto el : cur){
            if (no[ord[el][nd - D[el]]] == nd) I[el] = 1;
        }
        int cn = 0;
        for (auto el : cur){
            if (I[el]) ans[el]++;
            if (T[el] == ord[el][nd - D[el]]) cn++;
        }
        if (cn > 0){
            for (auto el : cur){
                if (T[el] != ord[el][nd - D[el]]) ncur.push_back(el);
            }
            swap(cur, ncur);
            ncur.clear();
        }
        nd++;
    }
    return ans;
}
