#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second

const int mxN = 5005;
ll n,d[mxN],m,s[mxN],t[mxN],dis[mxN],tam[mxN];
bool val[mxN];
ll ans[mxN];
map<pair<ll,ll>,vector<ll>> mp;
vector<ll> v[mxN];

bool dfs(ll at, ll par, ll i){
	if(at == t[i]){
		tam[i] = dis[at];
		mp[{dis[at], at}].pb(i);
		return true;
	}
	bool ok = false;
	for(auto it : v[at]){
		if(it == par) continue;
		dis[it] = dis[at] + 1;
		if(dfs(it, at, i)) ok = true;
	}
	if(ok){
		mp[{dis[at], at}].pb(i);
		return true;
	}
	return false;
}

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
){
    n = R.size() + 1;
    m = D.size();
    for(auto it : R){
    	v[it.ff].pb(it.sd);
    	v[it.sd].pb(it.ff);
	}
	for(int i = 0; i < m; i++) ans[i] = 1e13;
	for(int i = 0; i < m; i++){
		d[i] = D[i];
		s[i] = S[i];
		t[i] = T[i];
		val[i] = I[i];
		if(val[i]) ans[i] = D[i];
		dis[s[i]] = d[i];
		dfs(s[i], s[i], i);
	}
	for(auto &it : mp){
		bool ok = false;
		for(auto &i : it.sd) if(val[i]) ok = true;
		if(ok) for(auto &i : it.sd){
			if(val[i]) continue;
			val[i] = 1;
			ans[i] = min(ans[i], it.ff.ff);
		}
	}
	vector<int> res;
	for(int i = 0; i < m; i++){
		res.pb(max(0LL, tam[i] - ans[i] + 1));
	}
	return res;
}
