#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pb push_back

const int N = 5e3 + 5;
int d[N][N], to[N][N], ss;
vector<int> g[N];
void dfs(int s, int e = -1) {
    for (auto u : g[s]) {
        if (u == e) continue;
        d[ss][u] = d[ss][s]+1;
        to[u][ss] = s;
        dfs(u, s);
    }
}
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 c = 0;
    int n = R.size()+1;
    for (auto [u, v] : R)   g[u].pb(v), g[v].pb(u);
    for (int i = 0; i < n; ++i) {
        ss = i;
        dfs(i);
    }
    ll f[n];
    fill(f, f+n, -1);
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
    for (int i = 0; i < D.size(); ++i) {
        pq.push({D[i], I[i], i, S[i]});
    }
    vector<int> a(D.size(), n);
    for (int i = 0; i < n; ++i) {
        if (I[i])   a[i] = S[i];
    }
    while (!pq.empty()) {
        auto [d, nb, u, c] = pq.top();
       // cout << d << ' ' << u << ' ' << c << endl;
        pq.pop();
        if (I[u])   f[c] = d;
        if (!I[u] && f[c] == d)  I[u] = 1, a[u] = c;
        if (c != T[u])  pq.push({d+1, -I[u], u, to[c][T[u]]});
    }

    for (int i = 0; i < D.size(); ++i) {
        if (a[i] < n)   a[i] = d[a[i]][T[i]]+1;
        else
            a[i] = 0;
    }
    return a;
}
