#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
vector<int>valtime;
vector<int>lastroot;
dsu(int n){
root = vector<int>(n);
iota(root.begin(),root.end(),0);
siz=vector<int>(n,1);
valtime = vector<int>(n,1e9);
lastroot = vector<int>(n,-1);
}
void makeVal(int x, int tim){
x=findRoot(x);
valtime[x]=min(valtime[x],tim);
}
bool unite(int x, int y, int tim){
x=findRoot(x);
y=findRoot(y);
//cout << "turned into " << x << " " << y << "\n";
if(x==y){
makeVal(x,tim);
//cout << "cycle found\n";
return 0;
}
if(siz[x]<siz[y]){
//cout << "swapped\n";
swap(x,y);
}
//x is greater now
lastroot[y]=tim;
//as soon as timth edge was added y ceased to be root so this is non inclusive
siz[x]+=siz[y];
root[y]=x;
if(valtime[y]<1e9){
//if y comp is valid then x is also now valid
//cout << y << " was valid\n";
makeVal(x,tim);
}
return 1;
}
int findRoot(int x){
if(x==root[x]){
return x;
}
return findRoot(root[x]);
}
};
vector<array<int,3>>edges;
int n,m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N;
m=M;
for(int i = 0;i<m;i++){
edges.push_back({W[i],U[i],V[i]});
}
sort(edges.begin(),edges.end());
}
int getMinimumFuelCapacity(int x, int y) {
int d[n];
fill(d,d+n,0);
dsu ds(n);
for(int i = 0;i<m;i++){
int a = edges[i][1];
int b = edges[i][2];
//cout << "uniting " << a << " " << b << "\n";
ds.unite(a,b,i);
//cout << "united " << a << " " << b << "\n";
d[a]++;
d[b]++;
if(d[a]>=3||d[b]>=3){
ds.makeVal(a,i);
}
if(ds.findRoot(x)==ds.findRoot(y)&&ds.valtime[ds.findRoot(x)]<1e9){
return edges[i][0];
}
}
return -1;
}
