#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1000000005;
#define ff first
#define ss second
vector<pair<int, pair<int, int> > > edge;
vector<pair<int, int> > dsu[N];
int ans[N];
int d[N];
vector<int> gr[N];
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
cerr<<"BEGIN";
for(int i = 0; i < N; ++i)
ans[i] = INF;
for(int i = 0; i < N; ++i){
dsu[i].push_back({0, i});
gr[i].push_back(i);
}
for(int i = 0; i < M; ++i)
edge.push_back({W[i], {V[i], U[i]}});
sort(edge.begin(), edge.end());
for(auto& wtf : edge){
int v = wtf.ss.ff;
int u = wtf.ss.ss;
int w = wtf.ff;
int vv = dsu[v].back().ss;
int uu = dsu[u].back().ss;
if(vv == uu){
ans[vv] = min(ans[vv], w);
continue;
}
++d[v];
++d[u];
if(gr[vv].size() > gr[uu].size()){
swap(vv, uu);
swap(v, u);
}
ans[uu] = min(ans[uu], max(w, ans[vv]));
if(d[v] >= 3 || d[u] >= 3){
ans[uu] = min(ans[uu], w);
}
for(auto& x : gr[vv]){
gr[uu].push_back(x);
dsu[x].push_back({w, uu});
}
}
}
int getMinimumFuelCapacity(int x, int y){
int ix = dsu[x].size() - 1;
int iy = dsu[y].size() - 1;
int w = INF, mn = INF;
while(ix >= 0 && iy >= 0 && dsu[x][ix].ss == dsu[y][iy].ss){
w = max(dsu[x][ix].ff, dsu[y][iy].ff);
mn = min(mn, max(w, ans[dsu[x][ix].ss]));
--ix; --iy;
}
w = max(w, mn);
return (w == INF ? -1 : w);
}
