#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
const int N = 3e5 + 10;
const int Log = 20;
vector<pair<int, pii>> E;
int sp[Log][N], dep[N], wp[N];
int par[N], gd[N], la;
int deg[N], n, m;
int Find(int u){
if(par[u] == u) return u;
return par[u] = Find(par[u]);
}
void Unite(int u, int v, int w){
u = Find(u);
v = Find(v);
if(u == v){
la ++;
gd[la] = 1;
par[u] = la;
wp[u] = w;
sp[0][u] = la;
return ;
}
la ++;
par[u] = la;
par[v] = la;
wp[u] = w;
wp[v] = w;
sp[0][u] = la;
sp[0][v] = la;
gd[la] = gd[v] | gd[u];
}
void init(int n2, int m2, vector<int> U, vector<int> V, vector<int> W) {
n = n2;
m = m2;
for(int i = 0; i < m; i++)
E.pb({W[i], {U[i], V[i]}});
la = n - 1;
sort(all(E));
memset(gd, 0, sizeof gd);
memset(deg, 0, sizeof deg);
iota(par, par + N, 0);
memset(sp, 0, sizeof sp);
memset(wp, 0, sizeof wp);
memset(dep, 0, sizeof dep);
int u, v, w;
for(auto ob : E){
u = ob.S.F;
v = ob.S.S;
w = ob.F;
Unite(u, v, w);
deg[u] ++;
deg[v] ++;
if(max(deg[u], deg[v]) >= 3){
gd[Find(u)] = 1;
}
}
sp[0][la] = la;
for(int l = 1; l < Log; l++)
for(int i = 0; i <= la; i++)
sp[l][i] = sp[l - 1][sp[l - 1][i]];
dep[la] = 0;
for(int i = la - 1; i >= 0; i--)
dep[i] = dep[sp[0][i]] + 1;
}
int getMinimumFuelCapacity(int X, int Y){
if(dep[X] < dep[Y]) swap(X, Y);
//cerr << "! " << dep[X] << ' ' << dep[Y] << '\n';
int h = dep[X] - dep[Y];
for(int l = 0; l < Log; l++)
if(h >> l & 1)
X = sp[l][X];
for(int l = Log - 1; l >= 0; l--){
if((sp[l][X] != sp[l][Y]) || (gd[sp[l][X]] == 0)){
X = sp[l][X];
Y = sp[l][Y];
}
}
//cerr << "# " << X << ' ' << Y << '\n';
int res = max(wp[X], wp[Y]);
X = sp[0][X];
Y = sp[0][Y];
if((X != Y) || (gd[X] == 0))
return -1;
return res;
}
/*
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
*/
