#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
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, lg = 17, N = 1e5 + 5;
vector<int> needs(N, inf);
vector<vector<pair<int, int>>> g(N);
vector jump(lg, vector(N, make_pair(-1, 0)));
vector<int> tin(N), tout(N);
int n, z;
void dfs(int u) {
for (int i = 1; i < lg and u; i++) {
jump[i][u].ff = jump[i - 1][jump[i - 1][u].ff].ff;
if (jump[i][u].ff == -1) break;
jump[i][u].ss = max(jump[i - 1][u].ss, jump[i - 1][jump[i - 1][u].ff].ss);
}
tin[u] = ++z;
for (auto [v, w]: g[u]) {
if (tin[v]) continue;
jump[0][v] = make_pair(u, w);
dfs(v);
}
tout[u] = ++z;
}
bool isPar(int u, int v) { return tin[u] <= tin[v] and tout[v] <= tout[u]; }
int lca(int u, int v) {
if (isPar(u, v)) return u;
if (isPar(v, u)) return v;
for (int i = lg - 1; i >= 0; i--) {
if (jump[i][u].ff != -1 and !isPar(jump[i][u].ff, v)) {
u = jump[i][u].ff;
}
}
return jump[0][u].ff;
}
int dist(int u, int v) {
int p = lca(u, v), res = 0;
for (int i = lg - 1; i >= 0; i--) {
if (jump[i][u].ff != -1 and isPar(p, jump[i][u].ff)) {
res = max(res, jump[i][u].ss);
u = jump[i][u].ff;
}
if (jump[i][v].ff != -1 and isPar(p, jump[i][v].ff)) {
res = max(res, jump[i][v].ss);
v = jump[i][v].ff;
}
}
assert(u == p and v == p);
return res;
}
void init(int _n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = _n;
vector<pair<int, int>> vec(m);
vector<int> cnt(n), p(n);
vector<bool> bad(n);
vector<vector<int>> child(n);
for (int i = 0; i < n; i++) {
child[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: child[u]) needs[x] = w;
continue;
}
// cout << U[i] << ' ' << V[i] << ' ' << w << endl;
g[U[i]].emplace_back(V[i], w);
g[V[i]].emplace_back(U[i], w);
now |= bad[u] | bad[v];
if (now and !bad[u]) for (int x: child[u]) needs[x] = w;
if (now and !bad[v]) for (int x: child[v]) needs[x] = w;
if (child[u].size() > child[v].size()) swap(u, v);
for (int x: child[u]) {
child[v].emplace_back(x);
p[x] = v;
}
child[u].clear();
bad[v] = now;
}
dfs(0);
}
int getMinimumFuelCapacity(int x, int y) {
int ans = max(needs[x], needs[y]);
ans = max(ans, dist(x, y));
return ans == inf ? -1 : ans;
}
