#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;
vector<int>gr[150016];
vector<int>pr(150016, -1), dist(15016, 0);
inline void dfs(int v, int pr, int cnt){
	for(auto x : gr[v]){
		if(x != prr){
			pr[x] = v;
			dist[x] = cnt + 1;
			dfs(x, v, g, cnt + 1);
		}
	}
}
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);
	}
	int check = 0;
	for(int i = 0; i < (int)D.size(); ++i){
		if(D[i] != (long long)1000000 * (long long)(i + 1)){
			check = 1;
			break;
		}
	}
	if(check == 0){
		dfs(0, -1, 0);
		for(int i = 0; i < (int)D.size(); ++i){
			if(I[i] != 1){
				res[i] = 0;
				continue;
			}
			int st = S[i];
			map<int, int>mp;
			while(st != -1){
				mp[st] = 1;
				st = pr[st];
			}
			st = T[i];
			while(st != -1){
				if(mp[st] == 1){
					break;
				}
				st = pr[st];
			}
			res[i] = dist[S[i]] + dist[T[i]] - dist[st] - dist[st] + 1;
		}
	}
	return res;
}
