#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
/*
a component becomes valid as soon as
there is either a loop or a node with degree 3+
if it is just a chain, clearly impossible
use persistent DSU and find for each node, the minimum time
until it is part of a valid component
*/
int n, m;
int curtime = 0;
const int MAXN = 1e5 + 5;
map<int, int> dsu[MAXN];
int sz[MAXN];
int mintime[MAXN];
bool good[MAXN];
int deg[MAXN];
vector<int> active_nodes[MAXN];
const int INF = 2e9;
int find(int node, int time) {
auto it = dsu[node].upper_bound(time);
it --;
if ((*it).second == node) return node;
return find((*it).second, time);
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
curtime = 0;
for (int i = 0; i < n; i ++) {
mintime[i] = INF;
dsu[i][0] = i;
active_nodes[i].push_back(i);
sz[i] = 1;
deg[i] = 0; good[i] = false;
}
vector<pair<int, pair<int, int>>> edges;
for (int i = 0; i < M; i ++) {
edges.push_back({W[i], {U[i], V[i]}});
}
sort(edges.begin(), edges.end());
for (auto ee : edges) {
int a = ee.second.first, b = ee.second.second;
curtime = ee.first;
bool madegood = false;
// check if made good
deg[a] ++; deg[b] ++;
if (deg[a] >= 3 || deg[b] >= 3)
madegood = true;
a = find(a, curtime); b = find(b, curtime);
if (a == b)
madegood = true;
// unite components
if (a != b) {
if (sz[a] > sz[b])
swap(a, b);
sz[b] += sz[a];
for (auto aa : active_nodes[a])
active_nodes[b].push_back(aa);
active_nodes[a].clear();
dsu[a][curtime] = b;
}
good[b] = good[b] | good[a] | madegood;
if (good[b]) {
for (auto aa : active_nodes[b])
mintime[aa] = curtime;
active_nodes[b].clear();
}
}
// for (int i = 0; i < n; i ++)
// cout << mintime[i] << " "; cout << endl;
}
int getMinimumFuelCapacity(int X, int Y) {
// lower bound
int req = min(mintime[X], mintime[Y]);
// find smallest time until they are in same component
curtime = 1;
while (X != Y) {
auto itx = dsu[X].lower_bound(curtime),
ity = dsu[Y].lower_bound(curtime);
int nextmin = 2e9;
if (itx != dsu[X].end() && X != (*itx).second)
nextmin = min(nextmin, (*itx).first);
if (ity != dsu[Y].end() && Y != (*ity).second)
nextmin = min(nextmin, (*ity).first);
// cout << X << " " << Y << " " << curtime << endl;
// cout << nextmin << endl;
curtime = nextmin;
if (itx != dsu[X].end() && (*itx).first == curtime)
X = (*itx).second;
if (ity != dsu[Y].end() && (*ity).first == curtime)
Y = (*ity).second;
}
int ans = max(req, curtime);
if (ans == INF)
return -1;
return ans;
}
