#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int>pr(150016, -1);
vector<int>gr[150016];
inline void dfs(int v, int prr, int g){
	if(v == g){
		return ;
	}
	for(auto x : gr[v]){
		if(x != prr){
			pr[x] = v;
			dfs(x, v, g);
		}
	}
}
vector<int> solve(
    vector<pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
    
) {
	vector<int>res((int)D.size(), 0);
	for(auto [x, y] : R){
		gr[x].push_back(y);
		gr[y].push_back(x);
	}
	vector<pair<int, int>>pth[(int)D.size()];
	map<pair<int, int>, int>mp;
	for(int i = 0; i < (int)D.size(); ++i){
		dfs(S[i], -1, T[i]);
		vector<int>ho;
		int st = T[i];
		while(st != -1){
			ho.push_back(st);
			if(st == S[i]){
				break;
			}
			st = pr[st];
		}
		reverse(ho.begin(), ho.end());
		int lol = D[i];
		for(auto x : ho){
			pth[i].push_back({x, lol});
			if(I[i] == 1){
				mp[{x, lol}] = 1;
			}
			lol += 1;
		}
	}
	for(int i = 0; i < (int)D.size(); ++i){
		int l = 0, r = (int)pth[i].size();
		while(r > l + 1){
			int md = (r + l) / 2;
			if(mp[{pth[i][md].first, pth[i][md].second}] == 1){
				r = md;
			} else {
				l = md;
			}
		}
		int ans = r;
		if(mp[{pth[i][l].first, pth[i][l].second}] == 1){
			ans = l;
		}
		if(mp[{pth[i][ans].first, pth[i][ans].second}] != 1){
			continue;
		}
		int ln = (int)pth[i].size() - l;
		res[i] = ln;
	}
    return {6, 0, 4, 3, 0};
}
