#include <bits/stdc++.h>
#include "swap.h"
#define MAX 305000
int n,m;
typedef std::pair<int,int> pii;
typedef std::pair<int,pii> pip;
std::vector<pip> tmp;
std::vector<pii> con[MAX];
int pai[MAX];
bool acabou[MAX];
std::vector<int> candidatos[MAX];
std::vector<int> unicos[MAX];
int conexoes[MAX];
int fins[MAX];
int up[MAX][25];
int ph[MAX][25];
int prof[MAX];
void dfs(int pos,int prev,int peso,int depth){
prof[pos]=depth;
up[pos][0]=prev;
ph[pos][0]=peso;
for(auto&x:con[pos]){
if(x.first==prev)continue;
dfs(x.first,pos,x.second,depth+1);
}
}
int find(int a){
if(pai[a]==a)
return a;
return pai[a]=find(pai[a]);
}
int peso=0;
void Union(int a,int b){
conexoes[a]++;
conexoes[b]++;
a=find(a);
b=find(b);
if(a==b)acabou[a]=true;
else {
con[a].push_back({b,peso});
con[b].push_back({a,peso});
pai[b]=a;
if(candidatos[b]>candidatos[a])std::swap(candidatos[a],candidatos[b]);
for(auto&x:candidatos[b]){
candidatos[a].push_back(x);
}
for(auto&x:unicos[b]){
unicos[a].push_back(x);
}
unicos[b].clear();
candidatos[b].clear();
acabou[a]=std::max(acabou[a],acabou[b]);
}
assert(unicos[a].size()<=4);
{
std::vector<int> v;
for(auto&x:unicos[a]){
if(conexoes[x]==1)v.push_back(x);
}
unicos[a]=v;
}
if(unicos[a].size()>2)acabou[a]=true;
if(acabou[a]){
for(auto&x:candidatos[a])fins[x]=peso;
candidatos[a].clear();
unicos[a].clear();
return;
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N;
m=M;
for(int i=0;i!=M;++i){
tmp.push_back({W[i],{U[i],V[i]}});
}
std::sort(tmp.begin(),tmp.end());
for(auto&x:fins)x=1e9;
for(int i=0;i!=N;++i){
pai[i]=i;
candidatos[i].push_back(i);
unicos[i].push_back(i);
}
for(auto&x:tmp){
peso=x.first;
int u = x.second.first,v=x.second.second;
Union(u,v);
}
dfs(0,-1,-1,0);
for(int j=1;j!=25;++j){
for(int i=0;i!=N;++i){
if(up[i][j-1]==-1){
up[i][j]=-1;
continue;
}
up[i][j]=up[up[i][j-1]][j-1];
ph[i][j]=std::max(ph[up[i][j-1]][j-1],ph[i][j-1]);
}
}
/* for(int i=0;i!=N;++i){
std::cout<<fins[i]<<" ";
}
std::cout<<"\n";*/
}
int lcaval(int x,int y){
if(prof[y]<prof[x])std::swap(x,y);
int ans=0;
for(int i=24;i!=-1;--i){
int prox = up[y][i];
if(prox==-1)continue;
if(prof[prox]>=prof[x]){
ans=std::max(ans,ph[y][i]);
y=prox;
}
}
assert(prof[x]==prof[y]);
/// std::cout<<x<<" "<<y<<"preprof\n";
for(int i=24;i!=-1;--i){
int a = up[y][i];
int b = up[x][i];
if(a==-1||b==-1)continue;
if(a!=b){
ans=std::max(ans,ph[y][i]);
ans=std::max(ans,ph[x][i]);
x=b;
y=a;
}
}
/// std::cout<<x<<" "<<y<<"<-\n";
if(x!=y){
ans=std::max(ans,ph[y][0]);
ans=std::max(ans,ph[x][0]);
x=up[x][0];
y=up[y][0];
}
///assert(x==y);
/// std::cout<<"Retorna "<<ans<<"\n";
/// std::cout<<x<<" "<<y<<"\n";
return ans;
}
int getMinimumFuelCapacity(int X, int Y) {
if(fins[X]==1e9&&fins[Y]==1e9)return -1;
///Proxima etapa: Achar o peso minimo entre o caminho de X e Y, a resposta sera max(min(fins[X],fins[Y]),caminho)
int ans = std::min(fins[X],fins[Y]);
return std::max(ans,lcaval(X,Y));
}
