#include "infection.h"
#include <bits/stdc++.h>
#include <vector>
#include <utility>

using namespace std;
const int N = 1e5+5e4+10;
vector<int> yol[N], g[N];
int from[N], bar[N];
void dfs(int a, int p) {
	from[a] = p;
	for (auto i: g[a])
		if (i != p)dfs(i, a);
}

std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<long long> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
) {
	int n = (int)R.size();
	for (auto [i, j]: R) {
		g[i].push_back(j);
		g[j].push_back(i);
		//cout << i << " " << j << endl;
	}
	
	int m = (int)S.size();
	for (int i = 0; i < m; ++i) {
		dfs(S[i], -1);
		int x = T[i];
		yol[i].push_back(-1);
		while (x != S[i]) {
			yol[i].push_back(x);
			x = from[x];
		}
		//cout << S[i] << " " << T[i] << ":\n";
		//for (auto j: yol[i])
			//cout << j << " ";
		//cout << '\n';
		//reverse(all(yol[i]));
	}
	
	vector<int> res(m);
	int sum = m;
	while (sum) {
		for (int i = 0; i < m; ++i) {
			if (S[i] == -1)continue;
			if (I[i])bar[S[i]] = 1;
		}
		for (int i = 0; i < m; ++i) {
			if (S[i] == -1)continue;
			if (bar[S[i]])res[i] += 1, I[i] = 1;
		}
		for (int i = 0; i < m; ++i) {
			if (S[i] == -1)continue;
			bar[S[i]] = 0;
			S[i] = yol[i].back(), yol[i].pop_back();
			if (S[i] == -1)sum -= 1;
		}
	}
	return res;
}
