#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int inf = 2e9;
int par[N], comp_size[N], merged[N], time_valid[N], deg[N];
int find(int a) {
while (par[a] != a) a = par[a];
return a;
}
void join(int a, int b, int time) {
deg[a]++;
deg[b]++;
bool athree = deg[a] >= 3;
bool bthree = deg[b] >= 3;
a = find(a);
b = find(b);
if (athree) time_valid[a] = min(time_valid[a], time);
if (bthree) time_valid[b] = min(time_valid[b], time);
if (a == b) {
time_valid[a] = min(time_valid[a], time);
return;
}
if (comp_size[a] < comp_size[b]) swap(a, b);
time_valid[a] = min(time_valid[a], max(time, time_valid[b]));
par[b] = a;
comp_size[a] += comp_size[b];
merged[b] = time;
}
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] = 0;
}
vector<int> edges(m);
iota(edges.begin(), edges.end(), 0);
sort(edges.begin(), edges.end(), [&] (auto &a, auto &b) {
return W[a] < W[b];
});
for (int &i: edges) {
int u = U[i];
int v = V[i];
int w = W[i];
join(u, v, w);
}
}
int getMinimumFuelCapacity(int X, int Y) {
// ans is max(min(valid on path to root), max(merge on path to lca))
int merge_time = 0;
int valid_time = inf;
int x = X;
int y = Y;
while(x != y) {
if (comp_size[x] > comp_size[y]) swap(x, y);
merge_time = max(merge_time, merged[x]);
valid_time = min(valid_time, max(merge_time, time_valid[x]));
x = par[x];
}
int ans = merge_time;
while(merged[x] != 0) {
merge_time = max(merge_time, merged[x]);
valid_time = min(valid_time, max(merge_time, time_valid[x]));
x = par[x];
}
valid_time = min(valid_time, max(merge_time, time_valid[x]));
ans = max(ans, valid_time);
if (ans == inf) return -1;
return ans;
}
