#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] ++;
mxd[u_] = max(mxd[u_], deg[u]);
mxd[v_] = max(mxd[v_], deg[v]);
int t = ++newn;
weg[t] = w;
mxd[t] = max(mxd[u_], mxd[v_]);
cyc[t] = cyc[u_] | cyc[v_] | (u_ == v_);
par[u_] = par[v_] = t;
un[u_] = un[v_] = t;
}
vector<pair<int, pii>> swe;
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);
}
jmp[newn] = newn;
dep[newn] = 0;
par[newn] = -1;
for(int i = newn - 1; i >= 0; --i) {
int p = par[i];
dep[i] = dep[p] + 1;
// printf("%d %d %d\n", i, par[i], weg[i]);
if(dep[p] - dep[jmp[p]] == dep[jmp[p]] - dep[jmp[jmp[p]]]) {
jmp[i] = jmp[jmp[p]];
} else {
jmp[i] = p;
}
l[i] = N;
r[i] = -1;
}
for(int i = 0; i < newn; ++i) {
if(i < n) {
l[i] = r[i] = i;
}
l[par[i]] = min(l[par[i]], l[i]);
r[par[i]] = max(r[par[i]], r[i]);
}
}
bool ok(int u, int v) {
return (cyc[u] || mxd[u] >= 3) && (l[u] <= v && 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];
}
