#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 = 200005;
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];
}

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);
	map<pair<int, int>,int> mp;
	for (int i = 0; i < m; ++i) {
		if (I[i] == 1) {
			int lc = lca(S[i], T[i]);
			int dist1 = herav(S[i], lc);
			int dist2 = herav(T[i], lc);
			pat[i] = (dist1 + dist2 + 1);
			mp[{S[i], T[i]}] = pat[i];
		}
	}
	for (int i = 0; i < m; ++i) {
		if (I[i] == 0) {
			pat[i] = mp[{S[i], T[i]}];
		}
	}
	return pat;
}
