#include "infection.h"
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <iomanip>
#include <random>
#include <chrono>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <string>
#include <cstring>

using namespace std;

#define ll long long
#define pb push_back
#define fr first
#define sc second

const int N = 5005;
const ll oo = 1000000000000000, MOD = 1000000007;

int a[N], timer, par[N], tin[N], tout[N], dist[N], up[N][23];
vector<int> g[N];
bool color[N];


void dfs(int u, int p) {
	par[u] = p;
	color[u] = 1;
	++timer;
	tin[u] = timer;
	up[u][0] = p;
	for (int i = 1; i <= 20; ++i) {
		up[u][i] = up[up[u][i - 1]][i - 1];
	}
	for (int num : g[u]) {
		if (color[num] == 0) {
			dist[num] = dist[u] + 1;
			dfs(num, u);
		}
	}
	++timer;
	tout[u] = timer;
}

bool upper(int x, int y) {
	return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int lca(int x, int y) {
	if (upper(x, y)) {
		return x;
	}
	if (upper(y, x)) {
		return y;
    }
	for (int i = 20; i >= 0; --i) {
		if (up[x][i] != 0) {
			if (upper(up[x][i], y) != 1) {
				x = up[x][i];
			}
		}
	}
	return up[x][0];
}

int herav(int x, int y) {
	return dist[x] - dist[y];
}

set<ll> stjamanak;
//map<ll, vector<int>> yndhanur;
//map<pair<ll, int>, vector<int>> hamarner;
vector<int> yndhanur[N];
vector<int> hamarner[N][N];

void gna(int x, int y, ll skzb, int delta,int ind) {
	while (x != y) {
		yndhanur[skzb].pb(x);
		hamarner[skzb][x].pb(ind);
		stjamanak.insert(skzb);
		x = par[x];
		skzb += delta;
	}
}

vector<int> solve(vector<std::pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
	int n = R.size();
	int m = S.size();
	//MAQRELLLLLL
	for (int i = 1; i <= n; ++i) {
		g[i].clear();
		for (int j = 20; j >= 0; --j) {
			up[i][j] = 0;
		}
		tin[i] = tout[i] = par[i] = dist[i] = color[i] = 0;
	}
	timer = 0;
	/////////
	for (int i = 0; i < R.size(); ++i) {
		R[i].fr++;
		R[i].sc++;
		g[R[i].fr].pb(R[i].sc);
		g[R[i].sc].pb(R[i].fr);
	}
	for(int i=0;i<m;++i){
		S[i]++;
		T[i]++;
		D[i]++;
	}
	dfs(1,0);
	vector<int> pat(m);
	vector<ll> varakvac(m), qanijamchampin(m);
	for (int i = 0; i < m; ++i) {
		int lc = lca(S[i], T[i]);
		int dist1 = herav(S[i], lc);
		int dist2 = herav(T[i], lc);
		gna(S[i], lc, D[i], 1, i);
		gna(T[i], lc, D[i] + dist1 + dist2, -1,i);
		yndhanur[D[i]+dist1].pb(lc);
		hamarner[D[i] + dist1][lc ].pb(i);
		stjamanak.insert(D[i] + dist1);
		if (I[i]) {
			varakvac[i] = D[i];
		}
		else {
			varakvac[i] = oo;
		}
		qanijamchampin[i] = dist1 + dist2;
	}
	for (ll jam : stjamanak) {
		for (int indnode : yndhanur[jam]) {
			ll mn = oo;
			bool fl = 0;
			for (int num : hamarner[jam][indnode]) {
				if (varakvac[num] != oo) {
					fl = 1;
				}
			}
			for (int num : hamarner[jam][indnode]) {
				if (fl) {
					varakvac[num] = min(varakvac[num], jam);
				}
			}
		}
	}
	for (int i = 0; i < m; ++i) {
		if (varakvac[i] == oo) {
			pat[i] = 0;
		}
		else {
			pat[i] = (D[i] + qanijamchampin[i]) - varakvac[i] + 1;
		}
	}
	return pat;
}
