#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
vector<pair<int,pair<int,int>>> edges;
set<pair<int,int>> pars[100001];
int par[100001],deg[100001];
vector<int> group[100001];
bool good[100001];
int find(int curr){
return curr == par[curr] ? curr : par[curr] = find(par[curr]);
}
void merge(int a , int b , int c){
int p1 = find(a) , p2 = find(b);
if((good[p2] && !good[p1]) || group[p1].size() < group[p2].size()){
swap(a,b),swap(p1,p2);
}
int pre = good[p1];
if(good[p1] || good[p2] || deg[a] > 1 || deg[b] > 1){
good[p1] = 1;
}
if(pre == 0 && good[p1]){
for(auto i : group[p1]){
pars[i].insert({c,p1});
}
}
deg[a] += 1 , deg[b] += 1;
for(auto i : group[p2]){
if(good[p1]){
pars[i].insert({c,p1});
}
group[p1].push_back(i);
par[i] = p1;
}
group[p2].clear();
}
void init(int N , int M , vector<int> U , vector<int> V , vector<int> W){
for(int i = 0 ; i < N ; i += 1){
par[i] = i;
pars[i].insert({0,i});
group[i] = {i};
}
for(int i = 0 ; i < M ; i += 1){
edges.push_back({W[i],{U[i],V[i]}});
}
sort(edges.begin(),edges.end());
for(auto i : edges){
int a = i.second.first , b = i.second.second , c = i.first;
if(find(a) == find(b)){
if(!good[find(a)]){
good[find(a)] = 1;
for(auto j : group[find(a)]){
pars[j].insert({c,find(a)});
}
}
continue;
}
merge(a,b,c);
}
}
int getMinimumFuelCapacity(int X , int Y){
for(auto i : pars[X]){
for(auto j : pars[Y]){
if(i.second == j.second){
return max(i.first,j.first);
}
}
}
return -1;
}
