#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int inf = 2e9;
int par[MAXN], comp_size[MAXN], merged[MAXN], time_valid[MAXN], deg[MAXN];
int find(int a) {
while (par[a] != a) a = par[a];
return a;
}
void join(int u, int v, int time) {
deg[u]++;
deg[v]++;
int a = find(u);
int b = find(v);
// A component is swappable if an internal node has degree >= 3 or it has a cycle
bool swappable_now = (deg[u] >= 3 || deg[v] >= 3 || a == b); // [cite: 124, 125, 136]
if (a == b) {
time_valid[a] = min(time_valid[a], time);
return;
}
if (comp_size[a] < comp_size[b]) swap(a, b);
// Inheritance: If either child was already swappable,
// the new component is swappable at the time they merge.
if (time_valid[a] < inf || time_valid[b] < inf || swappable_now) {
time_valid[a] = min({time_valid[a], time_valid[b], time}); //
}
par[b] = a;
comp_size[a] += comp_size[b];
merged[b] = time; // Time when b was merged into a parent
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < n; i++) {
comp_size[i] = 1;
par[i] = i;
time_valid[i] = inf;
merged[i] = -1; // Use -1 to distinguish from a 0-weight edge
deg[i] = 0;
}
vector<int> edges(m);
iota(edges.begin(), edges.end(), 0);
sort(edges.begin(), edges.end(), [&](int a, int b) {
return W[a] < W[b];
});
for (int i : edges) {
join(U[i], V[i], W[i]);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int merge_time = 0;
int x = X, y = Y;
// 1. Find the LCA and the time X and Y first connected
while (x != y) {
if (comp_size[x] > comp_size[y]) swap(x, y);
if (par[x] == x) break; // Reached root
merge_time = max(merge_time, merged[x]);
x = par[x];
}
if (x != y) return -1; // Not in same component [cite: 131]
// 2. Climb to the root to find the earliest swappable ancestor
// The answer is the weight of the node where the component first became swappable
int x_swappable = x;
int best_valid = inf;
// Walk up from the meeting point to find the lowest ancestor that is swappable
int curr = x;
while (true) {
if (time_valid[curr] < inf) {
best_valid = max(merge_time, time_valid[curr]);
break;
}
if (par[curr] == curr) break;
merge_time = max(merge_time, merged[curr]);
curr = par[curr];
}
if (best_valid == inf) return -1;
return best_valid;
}
