#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int maxn=100005, maxm=200005;
vector<vector<int>> up(maxn+maxm,vector<int>(20, -1));
vector<bool> able(maxn+maxm, 0);
vector<int> dep(maxn+maxm, 0),wei(maxn+maxm, 0), in(maxn, 0), clse(maxn+maxn, INT_MAX);
vector<pair<int,int>> ch(maxn+maxn, {-1, -1});
int lca(int a, int b){
if(dep[a] < dep[b])swap(a, b);
int raiseby=dep[a]-dep[b];
for(int i=0;i<20;i++)if((1<<i) & raiseby) a=up[a][i];
if(a==b)return a;
for(int i=19;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
assert(up[a][0]==up[b][0]);
return up[a][0];
}
vector<int> p(maxn+maxm, -1);
int par(int x){
if(p[x]==-1)return x;
return p[x]=par(p[x]);
}
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W) {
vector<int> ord(M); iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int a, int b){
return W[a]<W[b];
});
int nw=N;
for(int i=0;i<M;i++){
int c=ord[i];
int pa=par(U[c]), pb=par(V[c]);
in[U[c]]++, in[V[c]]++;
bool cable=able[pa] || able[pb]
|| (in[V[c]] >= 3) || (in[U[c]]>=3)
|| (pa==pb);
p[pa]=nw, p[pb]=nw;
ch[nw].f=pa;
up[pa][0]=nw, up[pb][0]=nw;
if(pa!=pb)ch[nw].s=pb;
wei[nw]=W[c];
able[nw]=cable;
nw++;
}
auto dfs=[&](auto && dfs, int x, int prv) -> void{
if(able[x])prv=wei[x];
clse[x]=prv;
if(ch[x].f != -1){
dep[ch[x].f]=dep[x]+1;
dfs(dfs, ch[x].f, prv);
}
if(ch[x].s != -1){
dep[ch[x].s]=dep[x]+1;
dfs(dfs, ch[x].s, prv);
}
};
dfs(dfs, nw-1, INT_MAX);
for(int j=1;j<20;j++){
for(int i=0;i<nw;i++){
int prv=up[i][j-1];
if(prv!=-1){
up[i][j]=up[prv][j-1];
}
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int anc=lca(X, Y);
if(clse[anc] == INT_MAX){
return -1;
}
else return clse[anc];
}
