#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std ;
#define aaa 400003
// #define aaa 203
int n,m ;
int gp[aaa] ;
vector <int> gps[aaa] ;
int ok[aaa] ;
int dsu(int x){
if (x==gp[x]) return x ;
gp[x]=dsu(gp[x]) ;
return gp[x] ;
}
void un(int a,int b,int nw){
a=dsu(a),b=dsu(b) ;
if (a==b){
if (ok[a]==INT_MAX) for (auto x : gps[a]) ok[x]=nw ;
return ;
}
if (gps[a].size()<gps[b].size()) swap(a,b) ;
for (auto x : gps[b]) gps[a].push_back(x) ;
gps[b].clear() ;
gp[dsu(b)]=dsu(a) ;
}
int gp2[aaa] ;
int dsu2(int x){
if (x==gp2[x]) return x ;
gp2[x]=dsu2(gp2[x]) ;
return gp2[x] ;
}
int anc[32][aaa] ;
int dep[aaa] ;
int ww[aaa] ;
vector <int> adj2[aaa] ;
void dfs(int x){
for (auto a : adj2[x]) dep[a]=dep[x]+1,dfs(a) ;
}
int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v) ;
for (int k = 31 ; k >= 0 ; k --){
if (dep[anc[k][u]]>=dep[v]) u=anc[k][u] ;
}
if (u==v) return u ;
for (int k = 31 ; k >= 0 ; k --){
if (anc[k][u]!=anc[k][v]) u=anc[k][u],v=anc[k][v] ;
}
return anc[0][u] ;
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N,m=M ;
int i,j ;
map <int,vector<pair<int,int>>> mp ;
vector <int> adj[aaa] ;
for (i = 0 ; i < n ; i ++) ok[i]=INT_MAX,gp[i]=i,gps[i].push_back(i) ;
for (i = 0 ; i < m ; i ++){
mp[W[i]].push_back({U[i],V[i]}) ;
// mp[W[i]].push_back({V[i],U[i]}) ;
}
for (auto [x,v] : mp){
for (auto [a,b] : v){
adj[a].push_back(b) ;
adj[b].push_back(a) ;
if (ok[a]!=INT_MAX&&ok[b]==INT_MAX) for (auto aa : gps[dsu(b)]) ok[aa]=x ;
if (ok[b]!=INT_MAX&&ok[a]==INT_MAX) for (auto aa : gps[dsu(a)]) ok[aa]=x ;
un(a,b,x) ;
if (adj[a].size()>=3){
if (ok[a]==INT_MAX){
for (auto aa : gps[dsu(a)]) ok[aa]=x ;
}
}
if (adj[b].size()>=3){
if (ok[b]==INT_MAX){
for (auto aa : gps[dsu(b)]) ok[aa]=x ;
}
}
}
}
// for (i = 0 ; i < n ; i ++) cout << ok[i] << " " ; cout << endl ;
for (i = 0 ; i < n+m ; i ++) gp2[i]=i ;
vector <pair<int,pair<int,int>>> adjj ;
for (i = 0 ; i < m ; i ++) adjj.push_back({W[i],{U[i],V[i]}}) ;
sort(adjj.begin(),adjj.end()) ;
int cnt=n ;
for (auto [w,abc] : adjj){
auto [a,b]=abc ;
if (dsu2(a)==dsu2(b)) continue ;
a=dsu2(a),b=dsu2(b) ;
gp2[a]=cnt,gp2[b]=cnt ;
anc[0][a]=cnt,anc[0][b]=cnt ;
adj2[cnt].push_back(a) ;
adj2[cnt].push_back(b) ;
ww[cnt]=w ;
anc[0][cnt]=cnt ;
cnt++ ;
}
dep[cnt-1]=0 ;
dfs(cnt-1) ;
for (int k = 1 ; k < 32 ; k ++){
for (i = 0 ; i < cnt ; i ++){
anc[k][i]=anc[k-1][anc[k-1][i]] ;
}
}
// cout << ww[lca(1,3)] << endl ;
}
int getMinimumFuelCapacity(int X, int Y) {
int mx=-1 ;
mx=max(mx,ok[X]) ;
mx=max(mx,ok[Y]) ;
mx=max(mx,ww[lca(X,Y)]) ;
if (mx==INT_MAX) mx=-1 ;
return mx;
}
