#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;

vector <int> g[150010];
int tin[150010];
int tout[150010];
int dist[150010];
int up[20][150010];
int TMR;
vector <int> path[150010];

void dfs(int v) {
    tin[v] = ++TMR;
    for (int k = 1; k < 20; k++)
        up[k][v] = up[k - 1][up[k - 1][v]];
    for (auto to : g[v]) {
        if (to == up[0][v]) continue;
        up[0][to] = v; dist[to] = dist[v] + 1;
        dfs(to);
    }
    tout[v] = ++TMR;
    return;
}

bool is_par(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca(int a, int b) {
    if (is_par(a, b)) return a;
    if (is_par(b, a)) return b;
    for (int k = 19; k >= 0; k--) {
        if (!is_par(up[k][a], b)) a = up[k][a];
    }
    return up[0][a];
}

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;
    int m = D.size();
    vector <int> ans(m);
    vector <int> F(m, 0);
    vector <bool> inf(n);
    for (int i = 0; i < n; i++)
        g[i].clear();
    for (auto to : R) {
        g[to.F].pb(to.S);
        g[to.S].pb(to.F);
    }
    TMR = 0;
    dist[0] = 1;
    dfs(0);

    bool fl4 = 1;
    for (int i = 0; i < m; i++)
        if (D[i] != i * 1'000'000) fl4 = 0;

    if (fl4) {
        for (int i = 0; i < m; i++) {
            if (I[i] == 0) ans[i] = 0;
            else {
                int v = lca(s[i], t[i]);
                ans[i] = dist[s[i]] + dist[t[i]] - dist[v] * 2;
            }
        }
        return ans;
    }

    if (n <= 5000 && m <= 5000) {

        for (int i = 0; i < m; i++) {
            vector <int> pth;
            int v = s[i];
            while (!(tin[v] <= tin[t[i]] && tout[t[i]] <= tout[v])) {
                pth.pb(v);
                v = up[0][v];
            }
            v = t[i];
            while (!(tin[v] <= tin[s[i]] && tout[s[i]] <= tout[v])) {
                path[i].pb(v);
                v = up[0][v];
            }
            path[i].pb(v);
            reverse(pth.begin(), pth.end());
            for (auto to : pth) path[i].pb(to);

    //        cerr << "! " << i << endl;
    //        for (auto to : path[i])
    //            cerr << to << " ";
    //        cerr << endl;
        }

        for (int d = 0; d < n + 5; d++) {
    //            cerr << "day " << d << endl;
            for (int i = 0; i < n; i++) inf[i] = 0;
            for (int i = 0; i < m; i++) {
                if (D[i] > d) continue;
                if (F[i]) continue;
                s[i] = path[i].back(); path[i].pop_back();
                if (I[i]) inf[s[i]] = 1;
    //    cerr << i << " " << s[i] << endl;
            }
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                if (F[i]) continue;
                cnt++;
                if (D[i] > d) continue;
                if (inf[s[i]]) I[i] = 1;
                ans[i] += I[i];
                if (path[i].size() == 0) F[i] = 1;
            }
            if (cnt == 0) break;
        }

        return ans;
    }

    return ans;
}