#include "bits/stdc++.h"
#include "infection.h"
#include <vector>
#include <utility>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
#define N 24
#define maxn 150005

vector<int> v[maxn];
int pr[maxn][N],lvl[maxn];
map<ll,map<ll,bool> > m;

void f(int nd,int par){
	pr[nd][0]=par;
	lvl[nd]=lvl[par]+1;
	for(int i=1; i<N; i++){
		pr[nd][i]=pr[pr[nd][i-1]][i-1];
	}
	for(auto u:v[nd]){
		if(u==par)continue;
		f(u,nd);
	}
}

int lca(int a,int b){
	if(lvl[a]<lvl[b])swap(a,b);
	int x=lvl[a]-lvl[b];
	while(x){
		int l=log2(x);
		a=pr[a][l];
		x-=(1<<l);
	}
	if(a==b)return a;
	x=0;
	while(1){
		if(pr[a][x]==pr[b][x]){
			if(x==0)return pr[a][x];
			a=pr[a][x-1];
			b=pr[b][x-1];
			x=-1;
		}
		x++;
	}
	return -1;
}

void fx(int a,int b,ll st){
	int lc=lca(a,b);
	vector<int> v,v1;
	while(a!=lc){
		v.pb(a);
		a=pr[a][0];
	}
	while(b!=lc){
		v1.pb(b);
		b=pr[b][0];
	}
	v.pb(lc);
	reverse(v1.begin(),v1.end());
	for(int i=0; i<v1.size(); i++)v.pb(v1[i]);
	for(ll i=0; i<v.size(); i++)m[v[i]][st+i]=1;
}

int get(int a,int b,ll st){
	int lc=lca(a,b),q=b;
	vector<int> v,v1;
	while(a!=lc){
		v.pb(a);
		a=pr[a][0];
	}
	while(b!=lc){
		v1.pb(b);
		b=pr[b][0];
	}
	v.pb(lc);
	reverse(v1.begin(),v1.end());
	for(int i=0; i<v1.size(); i++)v.pb(v1[i]);
	bool f=false;
	int cnt=0;
	bool w=false;
	for(ll i=0; i<v.size(); i++){
		if(f and !m[v[i]][st+i]){
			fx(v[i],q,st+i);
			w=true;
		}
		f=f|(m[v[i]][st+i]);
		if(f)cnt++;
	}
	if(w)return -1;
	return cnt;
}

vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I) {
	for(int i=0; i<R.size(); i++)R[i].ff++,R[i].ss++;
	for(int i=0; i<S.size(); i++)S[i]++,T[i]++;
	for(int i=0; i<R.size(); i++){
		v[R[i].ff].pb(R[i].ss);
		v[R[i].ss].pb(R[i].ff);
	}
	f(1,0);
	for(int i=0; i<S.size(); i++){
		if(I[i])fx(S[i],T[i],D[i]);
	}
	vector<int> ans;
	while(true){
		bool w=false;
		for(int i=0; i<S.size(); i++){
			int x=get(S[i],T[i],D[i]);
			ans.pb(x);
			w=w|(x==-1);
		}
		if(w){
			ans.clear();
		}else{
			break;
		}
	}
	return ans;
}