#include "swap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int maxm = 2e5 + 10;
const int maxv = maxn * 3;
struct Node {
int pa;
int s, e, w;
Node(void) : pa(-1), s(-1), e(-1), w(-1) {}
Node(int pa, int s, int e, int w) : pa(pa), s(s), e(e), w(w) {}
};
int V = 0;
int p[20][maxv], h[maxv];
Node info[maxv];
vector<int> adj[maxv];
int fnd(int x) {
if(info[x].pa == x) return x;
return info[x].pa = fnd(info[x].pa);
}
void uni(int a, int b, int w) {
int x = fnd(a), y = fnd(b);
if(x == y) {
if(!~info[x].s) return;
int z = ++V;
info[z] = Node(z, -1, -1, w);
p[0][x] = z;
info[x].pa = z;
return;
}
int z = ++V;
p[0][x] = p[0][y] = z;
info[x].pa = info[y].pa = z;
info[z] = Node(z, (info[x].s ^ info[x].e ^ a), (info[y].s ^ info[y].e ^ b), w);
bool af = (a == info[x].s || a == info[x].e), bf = (b == info[y].s || b == info[y].e);
if(!~info[x].s || !~info[y].s || !af || !bf) info[z].s = info[z].e = -1;
}
void dfs(int u) {
for(auto v : adj[u]) {
h[v] = h[u] + 1;
dfs(v);
}
}
void init(int N, int M, vector<int> _u, vector<int> _v, vector<int> _w) {
V = N;
for(int i = 1; i <= N; ++i) info[i] = Node(i, i, i, 0);
vector<pair<int, pii>> E;
for(int i = 0; i < M; ++i) E.eb(_w[i], pii(++_u[i], ++_v[i]));
sort(all(E));
for(auto [w, t] : E) uni(t.fi, t.se, w);
for(int i = 1; i <= V; ++i) if(~info[i].s) info[i].w = -1;
for(int i = 1; i < 20; ++i) for(int j = 1; j <= V; ++j) p[i][j] = p[i - 1][p[i - 1][j]];
for(int i = 1; i < V; ++i) adj[p[0][i]].eb(i);
dfs(V);
}
int lca(int u, int v) {
if(h[u] < h[v]) swap(u, v);
for(int i = 19; i >= 0; --i) if(h[u] - (1 << i) >= h[v]) u = p[i][u];
if(u == v) return u;
for(int i = 19; i >= 0; --i) if(p[i][u] != p[i][v]) {
u = p[i][u];
v = p[i][v];
}
return p[0][u];
}
int getMinimumFuelCapacity(int X, int Y) {
int Z = lca(++X, ++Y);
if(!~info[Z].s) return info[Z].w;
for(int i = 19; i >= 0; --i) if(~info[p[i][Z]].s) Z = p[i][Z];
return info[p[0][Z]].w;
}
