#include "swap.h"
#include <bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
vector<pair<int,int>> par[N];
int sz[N];
vector<int> group[N];
vector<pair<int,pair<int,int>>> groupval[N];
int ans[M];
int edgecnt;
void init(int n, int m,vector<int> u, vector<int> v, vector<int> w){
edgecnt = m;
vector<pair<int,int>> compress;
for(int i = 0;i<n;i++){
par[i].push_back({-1,i});
group[i].push_back(i);
groupval[i].push_back({-1,{-1,0}});
}
for(int i = 0;i<m;i++){
compress.push_back({w[i],i});
}
sort(compress.begin(),compress.end());
for(int i = 0;i<m;i++){
ans[i] = compress[i].first;
int x = compress[i].second;
if( group[par[u[x]].back().second].size() > group[par[v[x]].back().second].size()){
swap(u[x],v[x]);
}
sz[u[x]]++;
sz[v[x]]++;
int tmp = par[u[x]].back().second;
//cout << u[x] << " " << v[x] << endl;
//cout << par[u[x]].back().second << " a " << par[v[x]].back().second << endl;
if(par[u[x]].back().second == par[v[x]].back().second){
pair<int,pair<int,int>> nw = {i,{groupval[par[v[x]].back().second].back().second.first + 1,max({groupval[par[v[x]].back().second].back().second.second, groupval[tmp].back().second.second,sz[u[x]],sz[v[x]]})}};
//cout << nw.second.first << " b " << nw.second.second << endl;
groupval[par[v[x]].back().second].push_back(nw);
continue;
}
for(auto c:group[tmp]){
par[c].push_back({i,par[v[x]].back().second});
group[par[v[x]].back().second].push_back(c);
}
pair<int,pair<int,int>> nw = {i,{groupval[par[v[x]].back().second].back().second.first + groupval[tmp].back().second.first + 1,max({groupval[par[v[x]].back().second].back().second.second, groupval[tmp].back().second.second,sz[u[x]],sz[v[x]]})}};
//cout << nw.second.first << " b " << nw.second.second << endl;
group[tmp].clear();
groupval[par[v[x]].back().second].push_back(nw);
//cout << "hey" << endl;
//return;
}
}
bool ck(int x,int y,int val){
int groupx = prev(lower_bound(par[x].begin(),par[x].end(),make_pair(val+1,-1)))->second;
int groupy = prev(lower_bound(par[y].begin(),par[y].end(),make_pair(val+1,-1)))->second;
if(groupx != groupy)
return 0;
pair<int,int> tmp = prev(lower_bound(groupval[groupx].begin(),groupval[groupx].end(),make_pair(val+1,make_pair(-1,-1))))->second;
return (tmp.first > -1) || (tmp.second > 2);
}
int getMinimumFuelCapacity(int x, int y) {
int l = 0,r = edgecnt;
while(l < r){
int m = (l + r)/2;
if(ck(x,y,m)){
r = m;
}
else l = m+1;
}
if(r == edgecnt)return -1;
return ans[l];
}
