#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int,int,int>> edg;
int minyes[100100],abp[100100];
map<int,int> unpersist[100100];
vector<int>v[100100];
vector<pair<int,int>> roots;
int derot,N_;
void upd(int t,int p,int v){
unpersist[p][t]=v;
}
void do_a_merge(int &x,int &y,int t){
if(v[x].size()<v[y].size())
swap(x,y);
for(auto k:v[y])
upd(t,k,x),abp[k]=x,v[x].push_back(k);
v[y].clear();
}
int par[100100],deg[100100];
bitset<100100>yes;
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W) {
for(int i=1;i<=N;i++)
unpersist[i][-1]=i,abp[i]=i;
N_=N;
for(int i=1;i<=N;i++)
v[i].push_back(i);
for(int i=0;i<M;i++)
edg.push_back({W[i],++U[i],++V[i]});
for(auto&i:minyes)i=1e9+1;
sort(edg.begin(),edg.end());
int prevW=get<0>(edg[0]);
for(auto[w,u,v]:edg){
deg[u]++,deg[v]++;
if(deg[u]>2&&!yes[abp[u]])
yes[abp[u]]=1,minyes[abp[u]]=w;
if(deg[v]>2&&!yes[abp[v]])
yes[abp[v]]=1,minyes[abp[v]]=w;
u=abp[u],v=abp[v];
if(u-v) {
do_a_merge(u,v,w);
if(!yes[u]&&yes[v])
yes[u]=1,minyes[u]=w;
} else if(!yes[v])
yes[v]=1,minyes[v]=w;
prevW=w;
}
}
int ok(int t,int x,int y){
x=(--unpersist[x].upper_bound(t))->second;
y=(--unpersist[y].upper_bound(t))->second;
return x==y&&minyes[x]<=t;
}
int getMinimumFuelCapacity(int X,int Y) {
++X,++Y;
int l=1,r=1e9,res=-1;
while(l<=r){
int mid=l+r>>1;
if(ok(mid,X,Y)){
r=mid-1,res=mid;
} else {
l=mid+1;
}
}
return res;
}
