#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define db double
#define ll long long
#define ar array
template<typename T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
struct dsu {
vector<vector<int>> adj;
vector<int> deg, p, sub, tin, tout;
vector<bool> mark;
int who;
dsu() {}
dsu(int n, int m) : adj(n + m), deg(n), p(n + m), who(n), sub(n + m), tin(n + m), tout(n + m), mark(n + m) {
iota(all(p), 0);
}
int get(int v) {
return v == p[v] ? v : p[v] = get(p[v]);
}
void add(int x, int y) {
int ox = x, oy = y;
x = get(x), y = get(y);
p[x] = who, p[y] = who;
if (deg[ox] == 0) sub[who] += -1;
else if (deg[ox] == 1) sub[who] += 1;
if (deg[oy] == 0) sub[who] += -1;
else if (deg[oy] == 1) sub[who] += 1;
deg[ox]++, deg[oy]++;
if (deg[ox] > 2 || deg[oy] > 2) mark[who] = 1;
adj[who].emplace_back(x);
if (x != y) adj[who].emplace_back(y);
who++;
}
void process(int sx) {
int timer = 0;
auto dfs = [&](auto&& s, int v, int p) -> void {
tin[v] = timer++;
for (int u : adj[v]) if (u != p) {
s(s, u, v);
sub[v] += sub[u];
mark[v] = mark[v] || mark[u];
}
tout[v] = timer - 1;
};
dfs(dfs, sx, -1);
}
bool anc(int x, int y) {
return tin[x] <= tin[y] && tout[y] <= tout[x];
}
};
const int INF = 1e9;
vector<vector<ar<int, 3>>> adj;
vector<int> weights;
int n, m;
dsu d;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
adj.resize(N + 1);
d = dsu(n, m);
for (int i = 0; i < M; i++) {
adj[U[i]].push_back({V[i], W[i], i});
adj[V[i]].push_back({U[i], W[i], i});
}
vector<int> idx(M);
iota(all(idx), 0);
sort(all(idx), [&](int x, int y) { return W[x] < W[y]; });
for (int i = 0; i < M; i++) {
d.add(U[idx[i]], V[idx[i]]);
}
d.process(n + m - 1);
weights.resize(m);
for (int i = 0; i < m; i++) {
weights[i] = W[idx[i]];
}
}
int getMinimumFuelCapacity(int X, int Y) {
auto good = [&](int mid) -> bool {
return d.anc(mid + n, X) && d.anc(mid + n, Y) && (d.mark[mid + n] || d.sub[mid + n] == 0);
};
int l = 0, r = m - 1, ans = m - 1;
if (!good(r)) return -1;
while (l <= r) {
int mid = (l+r)/2;
if (good(mid)) ans = mid, r = mid-1;
else l = mid+1;
}
return weights[ans];
}
