#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
int father[100005],siz[100005],cap1[100005],cap2[100005],primu[100005],insus[100005],parent[100005];
int gas(int x)
{
if(father[x]!=x)
father[x]=gas(father[x]);
return father[x];
}
void unite(int x, int y, int t)
{
int rootx = gas(x), rooty = gas(y);
if(rootx==rooty)
{
primu[rootx] = min(primu[rootx], t);
return;
}
if(siz[rootx] < siz[rooty])
{
swap(rootx,rooty);
swap(x,y);
}
insus[rooty]=t;
father[rooty]=rootx;
parent[rooty]=rootx;
siz[rootx]+=siz[rooty];
if(primu[rootx]!=INF)
{
}
else if(primu[rooty]!=INF)
{
primu[rootx]=t;
}
else if(x==cap1[rootx] && y==cap1[rooty])
{
cap1[rootx]=cap2[rooty];
}
else if(x==cap1[rootx] && y==cap2[rooty])
{
cap1[rootx]=cap1[rooty];
}
else if(x==cap2[rootx] && y==cap1[rooty])
{
cap2[rootx]=cap2[rooty];
}
else if(x==cap2[rootx] && y==cap2[rooty])
{
cap2[rootx]=cap1[rooty];
}
else
{
primu[rootx]=t;
}
}
vector<pair<int,pair<int,int>>> edges;
vector<int> con[100005];
int tin[100005],tout[100005],timer;
int depth[100005];
void dfs(int nod)
{
tin[nod]=++timer;
for(auto adj:con[nod])
{
depth[adj]=depth[nod]+1;
dfs(adj);
}
tout[nod]=++timer;
}
bool isanc(int x, int y)
{
return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for(int i=0;i<M;i++)
edges.push_back({W[i],{U[i],V[i]}});
sort(edges.begin(),edges.end());
for(int i=0;i<N;i++)
{
parent[i]=-1;
father[i]=i;
siz[i]=1;
cap1[i]=cap2[i]=i;
primu[i]=INF;
}
for(int i=0;i<edges.size();i++)
{
unite(edges[i].second.first, edges[i].second.second, edges[i].first);
}
for(int i=0;i<N;i++)
if(parent[i]!=-1)
con[parent[i]].push_back(i);
for(int i=0;i<N;i++)
if(parent[i]==-1)
dfs(i);
}
int getMinimumFuelCapacity(int x, int y)
{
int mnm=INF,aux=0;
while(x!=-1 && !isanc(x,y))
{
aux = max(aux, insus[x]);
x = parent[x];
}
if(x==-1)
return -1;
while(y!=x)
{
aux = max(aux, insus[y]);
y = parent[y];
}
while(x!=-1)
{
mnm = min(mnm, max(aux, primu[x]));
aux = max(aux, insus[x]);
x = parent[x];
}
if(mnm==INF)
return -1;
else
return mnm;
}
