#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
struct dsu {
vector<int> p, size;
void init(int n) {
size.assign(n, 1);
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int get(int a) {
return p[a] == a ? a : p[a] = get(p[a]);
}
void merge(int a, int b) {
a = get(a); b = get(b);
if (a == b) return;
if (size[a] > size[b]) swap(a, b);
size[b] += size[a];
p[a] = b;
}
};
const int inf = 2e9;
vector<int> needs;
vector<tuple<int, int, int>> all;
int n;
void init(int _n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = _n;
needs.assign(n, inf);
vector<pair<int, int>> vec(m);
vector<int> cnt(n), p(n);
vector<bool> bad(n);
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
g[i] = {i};
p[i] = i;
}
for (int i = 0; i < m; i++) vec[i] = make_pair(W[i], i);
sort(vec.begin(), vec.end());
for (auto [w, i]: vec) {
cnt[U[i]]++, cnt[V[i]]++;
bool now = (cnt[U[i]] > 2) | (cnt[V[i]] > 2);
int u = p[U[i]], v = p[V[i]];
if (u == v) {
if (bad[u]) continue;
bad[u] = true;
for (int x: g[u]) needs[x] = w;
continue;
}
now |= bad[u] | bad[v];
if (now and !bad[u]) {
for (int x: g[u]) needs[x] = w;
}
if (now and !bad[v]) {
for (int x: g[v]) needs[x] = w;
}
// cout << u << ' ' << v << ' ' << now << ' ' << w << endl;
if (g[u].size() > g[v].size()) swap(u, v);
for (int x: g[u]) {
g[v].emplace_back(x);
p[x] = v;
}
g[u].clear();
bad[v] = now;
}
all.resize(m);
for (int i = 0; i < m; i++) all[i] = tuple{vec[i].first, U[vec[i].second], V[vec[i].second]};
}
int getMinimumFuelCapacity(int x, int y) {
int ans = max(needs[x], needs[y]);
dsu ds; ds.init(n);
for (auto [w, u, v]: all) {
ds.merge(u, v);
if (ds.get(x) == ds.get(y)) {
ans = max(ans, w);
break;
}
}
return ans == inf ? -1 : ans;
}
