#include<bits/stdc++.h>
using namespace std;
vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T,vector<bool> I){
    int n = (int)R.size() + 1, m = (int)D.size();
    for(int i = 0; i < n - 1; i++){
        R[i].first++; R[i].second++;
    }
    for(int i = 0; i < m; i++){
        S[i]++; T[i]++;
    }
    vector<int> adj[n + 1];
    for(auto [x, y] : R){
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vector<int> d(n + 1), par(n + 1);
    vector<vector<int>> up(n + 1, vector<int>(20));
    function<void(int, int)> dfs = [&](int v, int p){
        d[v] = d[p] + 1;
        up[v][0] = p; par[v] = p;
        for(int i = 1; i < 20; i++) up[v][i] = up[up[v][i - 1]][i - 1];
        for(auto x : adj[v]){
            if(x == p) continue;
            dfs(x, v);
        }
    };
    dfs(1, 0);
    auto lca = [&](int a, int b){
        if(d[a] < d[b]) swap(a, b);
        int k = d[a] - d[b];
        for(int i = 19; i >= 0; i--){
            if(k & (1 << i)) a = up[a][i];
        }
        if(a == b) return a;
        for(int i = 19; i >= 0; i--){
            if(up[a][i] != up[b][i]){
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    };
    auto dist = [&](int a, int b){
        return d[a] + d[b] - 2 * d[lca(a, b)] + 1;
    };
    auto nxt = [&](int a, int b){
        int l = lca(a, b);
        if(d[l] < d[a]) return par[a];
        int k = d[b] - d[a] - 1;
        int v = b;
        for(int i = 19; i >= 0; i--){
            if(k & (1 << i)){
                v = up[v][i];
            }
        }
        return v;
    };
    vector<int> ans(m), val(n + 1), fix(m), cur(m);
    for(int i = 0; i < m; i++) if(I[i]) cur[i] = 1;
    for(int d = 0; d <= 5000; d++){
        for(int i = 0; i < m; i++){
            if(fix[i] || D[i] > d) continue;
            int x = nxt(S[i], T[i]);
            val[x] |= cur[i];
            S[i] = x;
        }
        for(int i = 0; i < m; i++){
            if(fix[i]) continue;
            cur[i] |= val[S[i]];
            if(cur[i] && !ans[i]) ans[i] = dist(S[i], T[i]);
            if(S[i] == T[i]) fix[i] = 1;
        }
        for(int i = 1; i <= n; i++) val[i] = 0;
    }
    return ans;
}