#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
vector<int>valtime;
vector<int>lastroot;
vector<int>d;
vector<vector<int>>g;
int n;
dsu(int nn){
n=nn;
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);
d=vector<int>(n);
g=vector<vector<int>>(n);
}
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]);
}
void dfs(int st, int dep, int p){
d[st]=dep;
for(int i : g[st]){
if(i==p){
continue;
}
dfs(i,dep+1,st);
}
}
void pre(){
//ok so all should be connected now and must do precomp for depth and all
int r = findRoot(0);
//all god is root now so depth 0
//first it is time to make the tree
for(int i = 0;i<n;i++){
if(i==r)
continue;
g[i].push_back(root[i]);
g[root[i]].push_back(i);
}
//tree made now dfs
dfs(r,0,-1);
//ok so depths done which means pre over now must make main thingy
}
int bestTime(int x, int y){
//TODO: will make corner case for -1s
if(d[x]<d[y]){
swap(x,y);
}
int ans = -1;
while(d[x]>d[y]){
ans=max(ans,lastroot[x]);
x=root[x];
}
//ok now both at same depth
while(x!=y){
ans=max(ans,lastroot[x]);
ans=max(ans,lastroot[y]);
x=root[x];
y=root[y];
}
//ok now minimum time for them to be connected is here now minimum time for validity is to be discovered
//will only make x go up now
while(valtime[x]==1e9){
ans=max(ans,lastroot[x]);
x=root[x];
}
//ok so now it should be valid so just max
ans=max(ans,valtime[x]);
return ans;
}
};
vector<array<int,3>>edges;
int n,m;
bool val = 1;
dsu ds(1e5+5);
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 d[n];
fill(d,d+n,0);
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);
}
}
ds.pre();
val=(ds.valtime[ds.findRoot(0)]!=1e9);
}
int getMinimumFuelCapacity(int x, int y) {
if(!val)
return -1;
return edges[ds.bestTime(x,y)][0];
}
