#include "swap.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+12;
vector<pair<int,int>> g[N];
vector<int> gr[N],st[N];
int n,m,p[N],timer=0,t[N],e1[N],e2[N],first_time[N];
bool is[N];
int get(int v){
if(p[v] == v) return v;
return p[v] = get(p[v]);
}
int n1,tt[N],P[N];
void merge(int a,int b){
int vv,uu;
vv = a;
uu = b;
a = get(a);
b = get(b);
if(a == b){
if(!is[a]){
for(int j:st[a]){
first_time[j]=timer;
}
st[a].clear();
is[a]=1;
}
timer++;
return;
}
if((int)st[a].size() > (int)st[b].size()){
swap(vv,uu);
swap(a, b);
}
n1++;
tt[n1] = timer;
// cout << n1 << ' ' << P[a] << ' ' << P[b] << "x\n";
gr[n1].push_back(P[a]);
gr[n1].push_back(P[b]);
P[b] = n1;
p[a] = b;
for(int j:st[a]){
st[b].push_back(j);
}
st[a].clear();
if(is[b] || is[a] || (vv != e1[a] && vv != e2[a]) || (uu != e1[b] && uu != e2[b])) {
is[b]=1;
for(int j:st[b]){
first_time[j]=timer;
}
st[b].clear();
}else{
if(uu == e1[b]){
e1[b] = (vv == e1[a] ? e2[a] : e1[a]);
}else{
e2[b] = (vv == e1[a] ? e2[a] : e1[a]);
}
}
timer++;
}
int B = 20;
int up[N][20],tin[N],tout[N],tv;
void dfs(int v,int pr){
up[v][0] = pr;
tin[v] = tv++;
for(int i = 1;i < B;i++){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int to:gr[v]){
dfs(to,v);
}
tout[v] = tv++;
}
bool is_pr(int a,int b){
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int v,int u){
if(is_pr(v,u)) return v;
if(is_pr(u,v)) return u;
for(int i = B - 1;i >= 0;i--){
if(!is_pr(up[v][i],u)){
v = up[v][i];
}
}
return up[v][0];
}
vector <array<int, 3>> e;
void init(int nn, int mm,std::vector<int> u, std::vector<int> v, std::vector<int> w) {
memset(first_time,-1,sizeof(first_time));
n1 = n = nn;
m = mm;
for (int i = 1; i <= m; i++) {
e.push_back({w[i - 1], u[i - 1] + 1, v[i - 1] + 1});
}
sort(e.begin(), e.end());
for(int i = 1;i <= n;i++) {
P[i] =e1[i] = e2[i] = p[i] = i;
st[i].push_back(i);
}
for(auto [w,a,b]:e){
merge(a,b);
}
dfs(n1,n1);
}
void merge1(int a,int b){
a = get(a);
b = get(b);
p[a] = b;
}
int getMinimumFuelCapacity(int X, int Y) {
X++;Y++;
int f = max(first_time[X],max(tt[lca(X,Y)],first_time[Y]));
if(first_time[X] == -1 || first_time[Y] == -1) return -1;
return e[f][0];
}
