#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<functional>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<queue>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ll long long
#define ve vector
#define vi ve<int>
#define vvi ve<vi>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a= max(a, b)
#define all(a) a.begin(), a.end()
#define for0(i, n) for(int i= 0; i < n; ++i)
#define pll pair<ll, ll>
const int N = 15e4;
vi g[N];
vi pyt;
bool dfs(int v, int par, int nd) {
	pyt.push_back(v);
	if (nd == v) return 1;
	for (auto u : g[v]) {
		if (u == par) continue;
		if (dfs(u, v, nd)) return 1;
	}
	pyt.pop_back();
	return 0;
}
vector<int> solve(vector<pair<int, int>> r, vector<long long> d, vector<int> s, vector<int> t, vector<bool> is) {
	int n = r.size() + 1, m = d.size();
	for (auto [u, v] : r) {
		g[u].push_back(v); g[v].push_back(u);
	}
	vvi pyts(m);
	vi ans(m);
	ve vc(n, ve<pii>(0));
	for (int i = 0; i < m; ++i) {
		pyt.clear();
		dfs(s[i], s[i], t[i]);
		pyts[i] = pyt;
		if (is[i]) ans[i] = pyt.size();
		for0(j, pyt.size()) {
			vc[pyt[j]].push_back({ d[i] + j, i });
			//mp[{d[i] + j, pyt[j] }].push_back(i);
		}
	}
	for (int i = 0; i < n; ++i) sort(all(vc[i]));
	vi its(n, 0);
	while (true) {
		pll mn = { 1e18, 1e18 };
		for (int i = 0; i < n; ++i) {
			if (its[i] < vc[i].size()) chmin(mn, pll(vc[i][its[i]].first, i));
		}
		if (mn == pll{1e18, 1e18}) break;
		int j = mn.second;
		int fst = its[mn.second]; bool f = 0;
		while (its[j] < vc[j].size() && vc[j][its[j]].first == mn.first) {
			f |= is[vc[j][its[j]++].second];
		}
		if (f) {
			its[j] = fst;
			while (its[j] < vc[j].size() && vc[j][its[j]].first == mn.first) {
				int i = vc[j][its[j]].second;
				if (is[i] == 0) ans[i] = pyts[i].size() - (mn.first - d[i]);
				is[i] = f;
				++its[j];
			}
		}

	}
	return ans;
	
}