#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX=1e5+5;
int P[MAX];
bool isTree[MAX];
vector<int> S[MAX];
vector<iii> edges,history[MAX];
int find(int u) {
if(P[u]==u)
return u;
return P[u]=find(P[u]);
}
void merge(int u,int v,int w) {
if(S[u].size()>S[v].size())
swap(u,v);
P[v]=u;
int newIsTree=isTree[u]&isTree[v];
while(S[v].size()>0) {
int tmp=S[v].back();
S[v].pop_back();
S[u].push_back(tmp);
history[tmp].push_back({w,{u,newIsTree}});
}
}
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++) {
P[i]=i;
isTree[i]=true;
S[i].push_back(i);
history[i].push_back({2e9,{i,false}});
}
for(iii edge:edges) {
int u=find(edge.second.first),v=find(edge.second.second),w=edge.first;
if(u!=v)
merge(u,v,w);
else if(isTree[u]) {
isTree[u]=false;
for(int tmp:S[u])
history[tmp].push_back({w,{u,false}});
}
}
}
vector<ii> getHistory(int u) {
vector<ii> rs;
for(iii his:history[u])
if(!his.second.second)
rs.push_back({his.first,his.second.first});
return rs;
}
int getMinimumFuelCapacity(int X, int Y) {
vector<ii> hisX=getHistory(X),hisY=getHistory(Y);
int rs=-1;
while(hisX.size()>0&&hisY.size()>0&&hisX.back().second==hisY.back().second) {
rs=min(hisX.back().first,hisY.back().first);
hisX.pop_back(),hisY.pop_back();
}
return rs;
}
