#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<ll, ll, ll>
#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<int32_t> t, vector<bool> is) {

	int n = r.size() + 1, m = d.size(); 
	ve<int> ans(m);
	for (auto [u, v] : r) {
		g[u].push_back(v); g[v].push_back(u);
	}
	vvi pyts(m);
	
	ve<tiii> vc;
	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.push_back({ d[i] + j, pyt[j], i});
			//mp[{d[i] + j, pyt[j] }].push_back(i);
		}
	}
	sort(all(vc));
	pll tk = pll(get<0>(vc[0]), get<1>(vc[0]));
	int lst = 0;
	bool f = 1;
	for (int i = 0; i < vc.size(); ++i) {
		auto [dy, v, ind] = vc[i];
		if (lst == i) tk = pll(dy, v);
		f |= is[ind];
		if (i + 1 == vc.size() || pll(get<0>(vc[i + 1]), get<1>(vc[i + 1])) != tk) {

			if (f) {
				for (int j = lst; j <= i; ++j) {
					int in = get<2>(vc[j]);
					if (is[in] == 0) ans[in] = pyts[in].size() - (dy - d[in]);
					is[in] = 1;
				}
			}
			f = 0;
			lst = i + 1;
		}
	}
	return ans;
	
}