#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
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, long long>>pth[(int)D.size()];
	map<pair<int, long long>, int>mp;
	vector<pair<long long, int>>hh;
	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());
		hh.push_back({D[i], i});
		long long lol = D[i];
		for(auto x : ho){
			pth[i].push_back({x, lol});
			if(I[i] == 1){
				mp[{x, lol}] = 1;
			}
			lol += 1;
		}
	}
	sort(hh.begin(), hh.end());
	for(auto [x, y] : hh){
		int ind = y;
		int cnt = 0;
		for(auto [v, dd] : pth[ind]){
			if(cnt > 0){
				cnt += 1;
				mp[{v, dd}] = 1;
			} else {
				if(mp[{v, dd}] == 1){
					cnt += 1;
				} 
			}
		}
		res[ind] = cnt;
	}
	for(auto [x, y] : hh){
		int ind = y;
		int cnt = 0;
		for(auto [v, dd] : pth[ind]){
			if(cnt > 0){
				cnt += 1;
				mp[{v, dd}] = 1;
			} else {
				if(mp[{v, dd}] == 1){
					cnt += 1;
				} 
			}
		}
		res[ind] = cnt;
	}
	for(auto [x, y] : hh){
		int ind = y;
		int cnt = 0;
		for(auto [v, dd] : pth[ind]){
			if(cnt > 0){
				cnt += 1;
				mp[{v, dd}] = 1;
			} else {
				if(mp[{v, dd}] == 1){
					cnt += 1;
				} 
			}
		}
		res[ind] = cnt;
	}
	
    return res;
}
