#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int N, M;
vector<pair<int, pair<int, int>>> edges; // (W, index)
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
N = _N; M = _M;
for (int i = 0; i < M; i++)
edges.push_back(make_pair(W[i], make_pair(U[i], V[i])));
sort(edges.begin(), edges.end());
}
struct dsu {
vector<int> fa, sz, ok, mx_deg;
dsu(int n) {
fa.resize(n + 10);
iota(fa.begin(), fa.end(), 0);
ok.assign(n + 10, false);
mx_deg.assign(n + 10, 0);
sz.assign(n + 10, 1);
}
// representative for each component
// fa[all the nodes in the component] is the same
int find(int x) {
while (x != fa[x]) {
x = fa[x] = fa[fa[x]];
}
return x;
}
void merge(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) return;
if (sz[px] > sz[py]) swap(px, py);
fa[px] = py;
sz[py] += sz[px];
ok[py] = ok[px] || ok[py];
mx_deg[py] = max(mx_deg[py], mx_deg[px]);
if (mx_deg[py] >= 3) ok[py] = true;
}
bool same(int x, int y) {
int px = find(x);
int py = find(y);
return px == py;
}
};
int getMinimumFuelCapacity(int X, int Y) {
dsu D(N);
vector<int> deg(N);
for (int i = 0; i < M; i++) {
int w = edges[i].first;
int u = edges[i].second.first;
int v = edges[i].second.second;
if (D.same(u, v)) D.ok[D.find(u)] = 1;
deg[u]++; deg[v]++;
if (deg[u] >= 3) {
D.mx_deg[D.find(u)] = 3;
D.ok[D.find(u)] = 1;
}
if (deg[v] >= 3) {
D.mx_deg[D.find(v)] = 3;
D.ok[D.find(v)] = 1;
}
D.merge(u, v);
if (D.same(X, Y) && D.ok[D.find(X)] == 1) return w;
}
return -1;
}
