#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int par[MAXN], depth[MAXN], t[MAXN], third[MAXN], deg[MAXN];
int findSet(int u) {
return u == par[u] ? u : findSet(par[u]);
}
int h(int u) {
return u == par[u] ? 0 : 1 + h(par[u]);
}
bool merge(int u, int v, int w) {
u = findSet(u);
v = findSet(v);
if(u == v) return false;
if(depth[u] > depth[v]) swap(u, v);
par[u] = v;
depth[v] += depth[u] == depth[v];
third[v] = min(third[v], third[u]);
t[u] = w;
return true;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < N; ++i) {
par[i] = i;
third[i] = INT_MAX;
}
vector<tuple<int, int, int>> edge(M);
for(int i = 0; i < M; ++i) edge[i] = {W[i], U[i], V[i]};
sort(edge.begin(), edge.end());
for(auto [w, u, v] : edge) {
++deg[u], ++deg[v];
bool e = merge(u, v, w);
if(!e || max(deg[u], deg[v]) > 2) {
int x = findSet(u);
third[x] = min(third[x], w);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int Z = findSet(X);
int hx = h(X), hy = h(Y), ans = third[Z];
if(ans == INT_MAX) return -1;
while(hx != hy) {
if(hx > hy) {
ans = max(ans, t[X]);
X = par[X];
--hx;
} else {
ans = max(ans, t[Y]);
Y = par[Y];
--hy;
}
}
while(X != Y) {
ans = max(ans, max(t[X], t[Y]));
X = par[X];
Y = par[Y];
}
return ans;
}
