#include "swap.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=2e5+50;
const ll mod=1e9+7;
using namespace std;
int n,m,d[nmax],sz[nmax],p[nmax],gd[nmax],gud[nmax],x,y,rs,vl,mx[nmax],i,j;
vector<pair<int,pair<int,int> > >g;
vector<pair<int,int> >v[nmax];
vector<int>vc[nmax];
int fnd(int x)
{
if(p[x]==x)return x;
return p[x]=fnd(p[x]);
}
void uni(int x,int y,int z)
{
d[x]++,d[y]++;
int px=fnd(x),py=fnd(y),i;
if(px==py)
{
if(!gd[px])
{
gd[px]=1;
for(i=0;i<lun(vc[px]);i++)gud[vc[px][i]]=z;
}
return;
}
if(sz[px]<sz[py])
{
swap(px,py);
swap(x,y);
}
p[py]=px;
sz[px]+=sz[py];
mx[px]=max(max(mx[px],mx[py]),max(d[x],d[y]));
if(gd[px] && !gd[py])
{
for(i=0;i<lun(vc[py]);i++)gud[vc[py][i]]=z;
}
else if(!gd[px] && gd[py])
{
for(i=0;i<lun(vc[px]);i++)gud[vc[px][i]]=z;
}
for(i=0;i<lun(vc[py]);i++)
{
vc[px].pb(vc[py][i]);
v[vc[py][i]].pb(mkp(px,z));
}
vc[py].clear();
if(!gd[px] && !gd[py] && mx[px]>=3)
{
gd[px]=1;
for(i=0;i<lun(vc[px]);i++)gud[vc[px][i]]=z;
}
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W)
{
n=N,m=M;
for(i=0;i<m;i++)
{
U[i]++,V[i]++;
g.pb(mkp(W[i],mkp(U[i],V[i])));
}
sort(all(g));
for(i=1;i<=n;i++)
{
sz[i]=1;
p[i]=i;
v[i].pb(mkp(i,0));
vc[i].pb(i);
}
for(i=0;i<m;i++)
{
x=g[i].sc.fr,y=g[i].sc.sc;
uni(x,y,g[i].fr);
}
}
int getMinimumFuelCapacity(int x,int y)
{
x++,y++,rs=inf;
if(!gud[x])return -1;
for(i=0;i<lun(v[x]);i++)
{
vl=inf;
for(j=0;j<lun(v[y]);j++)
{
if(v[x][i].fr==v[y][j].fr)
{
vl=max(v[x][i].sc,v[y][j].sc);
break;
}
}
rs=min(rs,vl);
}
rs=max(rs,max(gud[x],gud[y]));
return rs;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
