#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int N = 3e5;
const int LOG = 19;
int par[N+2], val[N+2], deg[N+2], dep[N+2];
int anc[N+2][LOG+2];
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < N+M; i++) {
par[i] = i;
anc[i][0] = i;
val[i] = -1;
}
vector<iii> edge;
for (int i = 0; i < M; i++) {
edge.push_back({W[i],{U[i],V[i]}});
}
sort(edge.begin(),edge.end());
for (int i = 0; i < M; i++) {
int u = edge[i].se.fi;
int v = edge[i].se.se;
int w = edge[i].fi;
int pu = find(u);
int pv = find(v);
deg[u]++, deg[v]++;
par[pu] = par[pv] = N+i;
anc[pu][0] = anc[pv][0] = N+i;
val[N+i] = -1;
if (deg[u] >= 3 || deg[v] >= 3 || pu == pv || val[pu] != -1 || val[pv] != -1) val[N+i] = w;
}
for (int i = 1; i <= LOG; i++) {
for (int j = 0; j < N+M; j++) {
anc[j][i] = anc[anc[j][i-1]][i-1];
}
}
for (int i = N+M-2; i >= 0; i--) {
dep[i] = dep[anc[i][0]]+1;
}
}
int lca(int X, int Y) {
if (dep[X] < dep[Y]) swap(X,Y);
for (int i = LOG; i >= 0; i--) {
if (dep[X]-(1<<i) >= dep[Y]) {
X = anc[X][i];
}
}
if (X == Y) return X;
for (int i = LOG; i >= 0; i--) {
if (anc[X][i] != anc[Y][i]) {
X = anc[X][i];
Y = anc[Y][i];
}
}
return anc[X][0];
}
int getMinimumFuelCapacity(int X, int Y) {
if (find(X) != find(Y)) return -1;
int z = lca(X,Y);
// cout << ">> " << z << '\n';
if (val[z] != -1) return val[z];
for (int i = LOG; i >= 0; i--) {
if (dep[z] < (1<<i)) continue;
if (val[anc[z][i]] == -1) z = anc[z][i];
}
return val[anc[z][0]];
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/
