#include "swap.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const int maxn=1e9+10;
int deg[100010],tag[100010],wh[100010],dep[100010],jpt[100010][20],jpw[100010][20];
vector<int> e[100010];
struct Dsu{
int ori[100010]={},si[100010]={};
void init(int n){
for(int i=0;i<n;i++)ori[i]=i,si[i]=1;
return ;
}
int f(int a){
return a==ori[a]?a:f(ori[a]);
}
void onion(int a,int b,int w){
int ok=0;
if(deg[a]>=3||deg[b]>=3)ok=1;
a=f(a),b=f(b);
if(a==b){
wh[a]=min(wh[a],w);
return ;
}
if(si[a]>si[b])swap(a,b);
si[b]+=si[a];
ori[a]=b;
jpt[a][0]=b;
jpw[a][0]=w;
if(ok)wh[b]=min(wh[b],w);
e[a].push_back(b),e[b].push_back(a);
return;
}
}dsu;
void dfs(int now,int last){
dep[now]=dep[last]+1;
for(auto x:e[now]){
if(x==last)continue;
dfs(x,now);
wh[now]=min(wh[now],max(wh[x],jpw[x][0]));
}
return;
}
void dfs2(int now,int last,int w){
w=min(w,wh[now]);
wh[now]=min(wh[now],w);
for(auto x:e[now]){
if(x==last)continue;
dfs2(x,now,max(w,jpw[x][0]));
}
return ;
}
void init(int n, int m,vector<int> u, vector<int> v, vector<int> w) {
for(int i=0;i<n;i++)wh[i]=maxn;
dsu.init(n);
vector<pair<int,pair<int,int>>>edge;
for(int i=0;i<m;i++)edge.push_back({w[i],{u[i],v[i]}});
sort(edge.begin(),edge.end());
for(auto [x,y]:edge){
auto [q,r]=y;
deg[q]++;
deg[r]++;
dsu.onion(q,r,x);
}
for(int i=1;i<=18;i++){
for(int j=0;j<n;j++){
jpt[j][i]=jpt[jpt[j][i-1]][i-1];
jpw[j][i]=max(jpw[j][i-1],jpw[jpt[j][i-1]][i-1]);
}
}
for(int i=0;i<n;i++)if(i==dsu.ori[i])dfs(i,i),dfs2(i,i,maxn);
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int ans=0;
for(int i=18;i>=0;i--){
if(dep[u]-(1<<i)>=dep[v]){
//cout<<jpw[u][i]<<" "<<u<<" k\n";
ans=max(ans,jpw[u][i]);
u=jpt[u][i];
}
}
if(u==v){
//cout<<ans<<" "<<wh[u]<<"\n";
return max(ans,wh[u]);
}
for(int i=18;i>=0;i--){
if(jpt[u][i]!=jpt[v][i]){
ans=max(ans,jpw[u][i]);
ans=max(ans,jpw[v][i]);
u=jpt[u][i];
v=jpt[v][i];
}
}
ans=max(ans,jpw[u][0]);
ans=max(ans,jpw[v][0]);
u=jpt[u][0];
//cout<<ans<<" "<<wh[u]<<"\n";
return max(ans,wh[u]);
}
int getMinimumFuelCapacity(int u, int v) {
int ans=lca(u,v);
return ans==maxn?-1:ans;
}
