#include "infection.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

#define int long long

using namespace std;

using pii = pair<int, int>;

bool dfs(int id, int v, int p, int goal, int dep, vector<vector<int>> &g, 
        vector<tuple<int, int, int>> &e) {
    if (v == goal) {
        e.push_back({dep, v, id});
        return true;
    }
    for (int u : g[v]) {
        if (u != p) {
            if (dfs(id, u, v, goal, dep + 1, g, e)) {
                e.push_back({dep, v, id});
                return true;
            }
        }
    }
    return false;
}

vector<signed> solve(vector<pair<signed, signed>> R, vector<long long> D, vector<signed> S,
        vector<signed> T, vector<bool> I) {
    int n = R.size() + 1, m = D.size();
    vector<vector<int>> g(n);
    for (auto [x, y] : R) {
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<tuple<int, int, int>> e;
    vector<signed> ans(m);
    for (int i = 0; i < m; i++) {
        dfs(i, S[i], S[i], T[i], D[i], g, e);
    }

    sort(e.begin(), e.end());

    vector<int> v;
    int pp1 = -1, pp2 = -1;
    for (auto [p1, p2, y] : e) {
        if (!(pp1 == p1 && pp2 == p2)) {
            bool hasi = 0;
            for (int x : v) {
                hasi = hasi || I[x];
            }
            if (hasi) {
                for (int x : v) {
                    I[x] = 1;
                }
            }
            for (int x : v) {
                ans[x] += I[x];
            }
            v.clear();
        }

        v.push_back(y);
        pp1 = p1, pp2 = p2;
    }

    return ans;
}
