#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){
return a.second<b.second;
}
struct dsu{
vector <int> pa;
void init(int n){
pa.clear();
for (int i=0; i<=n; i++) pa.push_back(i);
}
int prt(int n){
if (pa[n]==n) return n;
return pa[n]=prt(pa[n]);
}
void unn(int u,int v){
pa[prt(u)]=pa[prt(v)];
}
};
int weight[200010],lb[200010],dep[200010];
vector <int> krt[200010];
void dfs1(int cur,int prv){
if (prv!=-1) dep[cur]=dep[prv]+1;
for (int i:krt[cur]) dfs1(i,cur);
if (lb[cur]) weight[cur]=max(lb[cur],min(weight[krt[cur][0]],weight[krt[cur][1]]));
}
void dfs2(int cur,int mn){
weight[cur]=min(weight[cur],mn);
for (int i:krt[cur]) dfs2(i,min(mn,weight[cur]));
}
int fa[20][2000010];
int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v];
for (int i=0; i<20; i++){
if (d&(1<<i)) u=fa[i][u];
}
if (u==v) return u;
for (int i=19; i>=0; i--){
if (fa[i][u]!=fa[i][v]){
u=fa[i][u];
v=fa[i][v];
}
}
return fa[0][u];
}
void init(int N,int M,vector <int> U,vector <int> V,vector <int> W){
pair <pair <int,int>,int> edg[M];
for (int i=0; i<M; i++) edg[i]={{U[i]+1,V[i]+1},W[i]};
sort(edg,edg+M,cmp);
dsu d;
d.init(2*N);
int cnt=N;
for (int i=0; i<=2*N; i++) weight[i]=2e9;
for (int i=0; i<M; i++){
int u=d.prt(edg[i].first.first),v=d.prt(edg[i].first.second);
if (u==v){
weight[edg[i].first.first]=min(weight[edg[i].first.first],edg[i].second);
weight[edg[i].first.second]=min(weight[edg[i].first.second],edg[i].second);
continue;
}
cnt++;
d.unn(u,cnt);
d.unn(v,cnt);
krt[cnt].push_back(u); krt[cnt].push_back(v);
fa[0][u]=cnt; fa[0][v]=cnt;
lb[cnt]=edg[i].second;
}
dfs1(cnt,-1);
dfs2(cnt,2e9);
for (int i=1; i<20; i++){
for (int j=1; j<=cnt; j++) fa[i][j]=fa[i-1][fa[i-1][j]];
}
}
int getMinimumFuelCapacity(int X,int Y){
X++; Y++;
int l=lca(X,Y);
int ans=weight[l];
if (ans>1e9) ans=-1;
return ans;
}
