#include "swap.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+1;
const int inf=2e9;
int L[mxn],R[mxn],cost[mxn];
int n,m;
vector<int> sorted;
struct reachability_tree {
int par[mxn];
int lineW[mxn];
int sz[mxn];
int start[mxn];
int end[mxn];
int pw[mxn];
vector<int> w[mxn];
vector<int> li[mxn];
void init(int n) {
for(int j=0;j<n;j++) {
sz[j]=1;
par[j]=j;
start[j]=j;
end[j]=j;
lineW[j]=inf;
}
}
int findrep(int u) {
return par[u]==u ? u : findrep(par[u]);
}
void join(int u,int v,int weight) {
int _u=findrep(u);
int _v=findrep(v);
if(_u==_v) {
lineW[_u]=min(lineW[_u],weight);
w[_u].push_back(weight);
li[_u].push_back(lineW[_u]);
return;
}
if(sz[_u]>sz[_v]) {
swap(_u,_v);
swap(u,v);
}
par[_u]=_v;
sz[_v]+=sz[_u];
pw[_u]=weight;
lineW[_v]=min(lineW[_v],lineW[_u]);
if(lineW[_v]==inf && ((u==start[_u] || u==end[_u]) && (v==start[_v] || v==end[_v]))) {
if(v==start[_v]) {
start[_v]=end[_v];
end[_v]=start[_u] ^ end[_u] ^ u;
} else {
end[_v]=start[_u] ^ end[_u] ^ u;
}
} else {
lineW[_v]=min(lineW[_v],weight);
}
w[_v].push_back(weight);
li[_v].push_back(lineW[_v]);
}
int goup(int u,int weight) {
while(par[u]!=u && pw[u]<=weight) {
u=par[u];
}
return u;
}
bool check(int x,int weight) {
int k=upper_bound(w[x].begin(),w[x].end(),weight)-w[x].begin();
if(k==0) return false;
int v=li[x][k-1];
return v<=weight;
}
} rt;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N;
m=M;
for(int i=0;i<M;i++) {
L[i]=U[i];
R[i]=V[i];
cost[i]=W[i];
sorted.push_back(i);
}
sort(sorted.begin(),sorted.end(),[](int a,int b) {
return cost[a]<cost[b];
});
rt.init(n);
for(int i=0;i<m;i++) {
int u=L[sorted[i]];
int v=R[sorted[i]];
int c=cost[sorted[i]];
rt.join(u,v,c);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int lo=0;
int hi=m-1;
int ans=-1;
while(lo<=hi) {
int m=lo+hi>>1;
int v=cost[sorted[m]];
int a=rt.goup(X,v);
int b=rt.goup(Y,v);
if(a==b && rt.check(a,v)) {
ans=v;
hi=m-1;
} else {
lo=m+1;
}
}
return ans;
}
