#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 2e9
const int N = 1e5, N3 = 3*N;
vector<int> g[N3];
int swp[N], p[N], sz[N], deg[N], ix[N];
int dep[N], tswp[N3], lswp[N3], wt[N3], up[N3][19];
int find(int x){
return x == p[x] ? x : p[x] = find(p[x]);
}
int unite(int x, int y){
int px = find(x);
int py = find(y);
if(sz[px] < sz[py]) swap(px, py);
if(px == py){
swp[px] = 1;
return px;
}
deg[x]++;
deg[y]++;
if(max(deg[x], deg[y]) >= 3) swp[px] = 1;
if(swp[px] or swp[py]) swp[px] = 1;
p[py] = px;
sz[px] += sz[py];
return px;
}
void dfs(int v, int l){
if(tswp[v]) l = v;
lswp[v] = l;
for(int ch : g[v]){
dep[ch] = dep[v]+1;
dfs(ch, l);
}
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
vector<tuple<int,int,int>> ed(m);
for(int i=0; i<m; i++){
ed[i] = {w[i], u[i], v[i]};
}
sort(ed.begin(), ed.end());
iota(p, p+n, 0);
iota(ix, ix+n, 0);
up[m-1+n][0] = -1;
for(int i=0; i<m; i++){
auto [w, a, b] = ed[i];
int pa = find(a);
int pb = find(b);
g[i+n].push_back(ix[pa]);
up[ix[pa]][0] = i+n;
if(pa != pb){
g[i+n].push_back(ix[pb]);
up[ix[pb]][0] = i+n;
}
int pr = unite(a, b);
tswp[i+n] = swp[pr];
wt[i+n] = w;
ix[pr] = i+n;
}
for(int j=1; j<19; j++){
for(int i=0; i<m+n; i++) up[i][j] = up[up[i][j-1]][j-1];
}
dep[m-1+n] = 0;
dfs(m-1+n, -1);
}
int getMinimumFuelCapacity(int a, int b){
if(dep[a] > dep[b]) swap(a, b);
int d = dep[b] - dep[a];
for(int i=0; i<19; i++) if(d & (1<<i)) b = up[b][i];
for(int i=18; i>=0; i--) if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
if(a != b) a = up[a][0];
return (lswp[a] == -1 ? -1 : wt[lswp[a]]);
}
