#include<bits/stdc++.h>
#include "swap.h"
#define ll long long
const int inf=1e9;
using namespace std;
vector<pair<int,pair<int,int>>>ed;
vector<pair<int,int>>dsu[100005];
int ans[100005],t[100005];
vector<int>g[100005];
void init(int n,int m,vector<int>x,vector<int>y,vector<int>w)
{
int i;
for(i=0;i<n;i++)
ans[i]=inf;
for(i=0;i<n;i++){
dsu[i].push_back({0,i});
g[i].push_back(i);
}
for(i=0;i<m;i++)
ed.push_back({w[i],{y[i],x[i]}});
sort(ed.begin(),ed.end());
for(auto &it:ed){
int y,x,w;
y=it.second.first;
x=it.second.second;
w=it.first;
int ty=dsu[y].back().second,tx=dsu[x].back().second;
if (ty==tx){
ans[ty]=min(ans[ty],w);
continue;
}
++t[y];
++t[x];
if (g[ty].size()>g[tx].size())
swap(tx,ty),swap(x,y);
ans[tx]=min(ans[tx],max(w,ans[ty]));
if (t[x]>=3 || t[y]>=3)
ans[tx]=min(ans[tx],w);
for(auto it2:g[ty]){
g[tx].push_back(it2);
dsu[it2].push_back({w,tx});
}
}
}
int getMinimumFuelCapacity(int x,int y)
{
int tx=dsu[x].size()-1,ty=dsu[y].size()-1;
int rez=inf,mini=inf;
while(tx>=0 && ty>=0 && dsu[x][tx].second==dsu[y][ty].second){
rez=max(dsu[x][tx].first,dsu[y][ty].first);
mini=min(mini,max(rez,ans[dsu[x][tx].second]));
tx--;
ty--;
}
rez=max(rez,mini);
if (rez==inf)
return -1;
return rez;
}
