#include "swap.h"
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
const int N = 300100;
const int M = 200100;
const int PW = 20;
vector<int> g[N];
int n, m, U[M], V[M], W[M], pre[N], lst, indx[N], deg[N], cost[N];
int ht[N], up[N][PW], tin[N], tout[N], tt = 0, id[N];
bool mrk[N], good[N];
bool cmp(int _x, int _y){
return (W[_x] < W[_y]);
}
int get(int x) { return (pre[x] == x ? x : pre[x] = get(pre[x])); }
void dfs(int v){
tin[v] = tt++;
for (int po = 1; po < PW; po++)
up[v][po] = up[up[v][po - 1]][po - 1];
for (int u : g[v]){
ht[u] = ht[v] + 1;
up[u][0] = v;
dfs(u);
}
tout[v] = tt++;
}
void init(int NN, int MM, std::vector<int> UU, std::vector<int> VV, std::vector<int> WW) {
n = NN; m = MM;
for (int i = 0; i < m; i++) {
U[i] = UU[i];
V[i] = VV[i];
W[i] = WW[i];
id[i] = i;
}
for (int i = 0; i < n; i++) {
pre[i] = i;
indx[i] = i;
good[i] = 0;
deg[i] = 0;
}
sort(id, id + m, cmp);
lst = n;
for (int it = 0; it < m; it++){
int i = id[it];
int x = get(U[i]);
int y = get(V[i]);
if (x == y){
if (!good[indx[x]]){
g[lst].PB(indx[x]);
good[lst] = 1;
indx[x] = lst;
cost[lst] = W[i];
lst++;
}
} else {
deg[U[i]]++;
deg[V[i]]++;
bool kok = (good[indx[x]] || good[indx[y]] || (deg[U[i]] > 2) || (deg[V[i]] > 2));
g[lst].PB(indx[x]);
g[lst].PB(indx[y]);
cost[lst] = W[i];
good[lst] = kok;
indx[x] = lst;
pre[y] = x;
lst++;
}
}
up[lst - 1][0] = lst - 1;
dfs(lst - 1);
}
bool upper(int a, int b){
return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
int lca(int a, int b){
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int po = PW - 1; po >= 0; po--)
if (!upper(up[a][po], b))
a = up[a][po];
return up[a][0];
}
int getMinimumFuelCapacity(int X, int Y) {
if (!good[lst - 1]) return -1;
int lc = lca(X, Y);
if (good[lc])
return cost[lc];
else {
for (int po = PW - 1; po >= 0; po--){
if (ht[lc] < (1 << po)) continue;
if (!good[up[lc][po]])
lc = up[lc][po];
}
return cost[up[lc][0]];
}
}
