#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
int n,m;
vector<piii>edgelist;
vector<int>isline,depths,grpsz;
vector<pii>parent,endpoints;
vector<vector<pii>>childlist;
int leader(int cn)
{
if(parent[cn].ff==cn){return cn;}
return leader(parent[cn].ff);
}
void dfsdate(int cn, int val)
{
isline[cn]=val;
for(pii child:childlist[cn])
{
dfsdate(child.ff,val);
}
}
void merge(int cn, int pn, int val, int a1, int a2)
{
if(grpsz[cn]<grpsz[pn])
{
swap(cn,pn);
swap(a1,a2);
}
if(grpsz[cn]==grpsz[pn]){grpsz[cn]++;}
if(isline[cn]!=0&&isline[pn]==0)dfsdate(pn,val);
if(isline[cn]==0&&isline[pn]!=0)dfsdate(cn,val);
parent[pn]=mp(cn,val);
childlist[cn].pb(mp(pn,val));
if((a1==endpoints[cn].ff||a1==endpoints[cn].ss)&&(a2==endpoints[pn].ff||a2==endpoints[pn].ss))
{
endpoints[cn]=mp(endpoints[cn].ff==a1?endpoints[cn].ss:endpoints[cn].ff,endpoints[pn].ff==a2?endpoints[pn].ss:endpoints[pn].ff);
}
else
{
if(isline[cn]==0)dfsdate(cn,val);
}
}
void dfs(int cn, int cd)
{
depths[cn]=cd;
for(pii child:childlist[cn])
{
dfs(child.ff,cd+1);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
n=N;m=M;
isline.resize(n,0);endpoints.resize(n);
parent.resize(n);depths.resize(n);childlist.resize(n);grpsz.resize(n,1);
for(int i=0;i<n;i++){parent[i]=mp(i,0);}
for(int i=0;i<n;i++){endpoints[i]=mp(i,i);}
for(int i=0;i<m;i++){edgelist.pb(mp(W[i],mp(U[i],V[i])));}
sort(edgelist.begin(),edgelist.end());
for(piii edge:edgelist)
{
int t1=leader(edge.ss.ff),t2=leader(edge.ss.ss);
if(t1==t2)
{
if(!isline[t1])dfsdate(t1,edge.ff);
}
else
{
merge(t1,t2,edge.ff,edge.ss.ff,edge.ss.ss);
}
}
dfs(leader(0),1);
}
int getMinimumFuelCapacity(int X, int Y)
{
if(isline[X]==0||isline[Y]==0)return -1;
int ans=max(isline[X],isline[Y]);
if(depths[X]>depths[Y]){swap(X,Y);}
while(depths[Y]>depths[X])
{
ans=max(parent[Y].ss,ans);
Y=parent[Y].ff;
}
while(Y!=X)
{
ans=max(parent[Y].ss,ans);
Y=parent[Y].ff;
ans=max(parent[X].ss,ans);
X=parent[X].ff;
}
return ans;
}
