#include "infection.h"
#include <vector>
#include <utility>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
using ll = long long;
#define V vector
#define VI V<int>
#define rep(i,a,b,step) for(int i=int(a);i<=int(b);i+=int(step))
#define repl(i,a,b,step) for(int i=int(a);i>=int(b);i-=int(step))
#define ff first
#define ss second
#define pq priority_queue
#define pb push_back
const ll inf = 1e18;
const int N = 5e3;
VI graph[N];
int d[N], ds[N][N], md[N][N];
bool dfs1(int u, int t, int p, V<bool>&mark) {
    if (u == t) {
        mark[u] = 1;
        return 1;
    }
    for (auto& i : graph[u])if (i != p and dfs1(i, t, u, mark)) {
        mark[u] = 1;
        return 1;
    }
    return 0;
}
VI pt;
void dfs2(int u, int p, int st) {
    pt.pb(u);
    for (auto& i : graph[u])if (i != p) {
        ds[st][i] = ds[st][u] + 1;
        if (pt.size() % 2 == 0)md[st][i] = pt[pt.size() / 2];
        else md[st][i] = -1;
        dfs2(i, u, st);
    }
    pt.pop_back();
}
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, m = D.size(), u, mid;
    V<ll>dist(m, inf);
    pq<pair<ll, int>, V<pair<ll, int>>, greater<>>q;
    V<V<bool>>mark(m, V<bool>(n));
    VI ans(m);
    rep(i, 0, n - 2, 1) {
        graph[R[i].ff].pb(R[i].ss);
        graph[R[i].ss].pb(R[i].ff);
    }
    rep(i, 0, m - 1, 1) {
        if (I[i]) {
            dist[i] = 0;
            q.push({ dist[i],i });
        }
        md[i][i] = i;
        dfs1(S[i], T[i], -1, mark[i]);
    }
    rep(i, 0, n - 1, 1) {
        ds[i][i] = 1;
        dfs2(i, -1, i);
    }
    pair<ll, int>cur;
    ll d;
    while (!q.empty()) {
        cur = q.top();
        q.pop();
        d = cur.ff;
        u = cur.ss;
        if (d != dist[u])continue;
        rep(i, 0, m - 1, 1) {
            if (md[S[u]][S[i]] != -1 and u != i) {
                mid = md[S[u]][S[i]];
                if (mark[u][mid] and mark[i][mid] and ds[mid][S[u]] >= dist[u] and dist[i] > ds[S[u]][S[i]] / 2) {
                    dist[i] = ds[S[u]][S[i]] / 2;
                    q.push({ dist[i],i });
                }
            }
        }
    }
   // rep(i, 0, m - 1, 1)cout << dist[i] << " \n"[i == m - 1];
    rep(i, 0, m - 1, 1)ans[i] = (dist[i] == inf ? 0 : max(0ll, ds[S[i]][T[i]] - dist[i]));
    return ans;
}