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

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second
#define ll long long

const int N = 150005;

vector <int> v[N];

vector<int> solve(
    vector<pair<int, int>> R,
    vector<ll> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I) {
    int n = SZ(R) + 1;
    for(int i = 0; i < n-1; i++) {
        R[i].ff++;
        R[i].ss++;
        v[R[i].ff].push_back(R[i].ss);
        v[R[i].ss].push_back(R[i].ff);
    }
    vector <vector <int>> ds(n+1, vector <int> (n+1, -1));
    for(int i = 1; i <= n; i++) {
        ds[i][i] = 0;
        queue <int> q;
        q.push(i);
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            for(auto j : v[x]) {
                if(ds[i][j] == -1) {
                    ds[i][j] = ds[i][x] + 1;
                    q.push(j);
                }
            }
        }
    }
    vector <vector <ll>> a, ac, ac1;
    int m = SZ(D);
    for(int i = 0; i < m; i++) {
        S[i]++;
        T[i]++;
        a.push_back({D[i], S[i], T[i], I[i], i});
    }//               0     1     2      3   4
    sort(a.begin(), a.end());
    int ind = 0;
    vector <int> inf(m, -1);
    while(ind < m or SZ(ac)) {
        while((ind < m) and (!SZ(ac) or ac.back()[0] == a[ind][0])) {
            ac.push_back(a[ind]);
            ind++;
        }
        vector <int> vis(n+1, 0);
        for(auto b : ac) {
            vis[b[1]] |= b[3];
        }
        for(auto &b : ac) {
            b[3] |= vis[b[1]];
            if(b[3] and inf[b[4]] == -1) inf[b[4]] = b[0];
        }
        for(auto &b : ac) {
            if(b[1] == b[2]) continue;
            b[0]++;
            for(auto x : v[b[1]]) {
                if(ds[b[2]][x] == ds[b[2]][b[1]] - 1) {
                    b[1] = x;
                    break;
                }
            }
            ac1.push_back(b);
        }
        ac.clear();
        swap(ac, ac1);
    }
    vector <int> ans;
    for(int i = 0; i < m; i++) {
        if(inf[i] == -1) {
            ans.push_back(0);
            continue;
        }
        ans.push_back(D[i] + ds[T[i]][S[i]] - inf[i] + 1);
    }
    return ans;
}
