#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include "swap.h"
#define X first
#define Y second
#define PB push_back
#define deb(...) //fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int LOG = 19;
const int N = 1 << LOG;
int un[N], jmp[N], par[N], dep[N];
int mxd[N], cyc[N], deg[N], weg[N], newn;
int l[N], r[N];
int trazi(int u) { return un[u] == -1 ? u : un[u] = trazi(un[u]); }
void unija(int u, int v, int w) {
int u_ = trazi(u);
int v_ = trazi(v);
deg[u] ++;
deg[v] ++;
int t = ++newn;
weg[t] = w;
mxd[t] = max({mxd[u_], mxd[v_], deg[u], deg[v]});
cyc[t] = cyc[u_] | cyc[v_] | (u_ == v_);
par[u_] = par[v_] = t;
un[u_] = un[v_] = t;
}
vector<pair<int, pii>> swe;
vector<int> g[N];
void dfs(int u, int &k) {
l[u] = k;
k += g[u].empty();
for(int v : g[u]) { dfs(v, k); }
r[u] = k;
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
newn = n - 1;
memset(un, -1, sizeof(un));
for(int i = 0; i < m; ++i) { swe.PB({W[i], {U[i], V[i]}}); }
sort(swe.begin(), swe.end());
for(pair<int, pii> &i : swe) {
unija(i.Y.X, i.Y.Y, i.X);
deb("%d %d %d\n", i.Y.X, i.Y.Y, i.X);
}
deb("\n");
jmp[newn] = newn;
dep[newn] = 0;
par[newn] = -1;
for(int i = newn - 1; i >= 0; --i) {
int p = par[i];
g[p].PB(i);
dep[i] = dep[p] + 1;
deb("%d %d %d, %d %d\n", i, par[i], weg[i], cyc[i], mxd[i]);
if(dep[p] - dep[jmp[p]] == dep[jmp[p]] - dep[jmp[jmp[p]]]) {
jmp[i] = jmp[jmp[p]];
} else {
jmp[i] = p;
}
}
int k = 0;
dfs(newn, k);
}
bool ok(int u, int v) {
return (cyc[u] || mxd[u] >= 3) && (l[u] <= l[v] && r[v] <= r[u]);
}
int getMinimumFuelCapacity(int x, int y) {
if(x == y) { return 0; }
for(; !ok(x, y); ) {
if(ok(jmp[x], y)) { x = par[x]; }
else {
if(jmp[x] == x) { return -1; }
x = jmp[x];
}
}
return weg[x];
}
