#include "swap.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
vector<pair<int,int>>adj[200005];
int cur;
int p[200005];
int in[200005];
int can[200005];
int n,m;
int pa[20][200005];
int mx[200005];
int lv[200005];
int fp(int a){
return p[a]==a?a:p[a]=fp(p[a]);
}
void un(int a,int b,int w){
if((fp(a))==(fp(b))){
if(can[fp(a)])return;
mx[fp(a)]=w;
can[fp(a)]=1;
return;
}
cur++;
adj[cur].push_back({fp(a),w});
adj[cur].push_back({fp(b),w});
if(can[fp(a)]||can[fp(b)])can[cur]=1;
in[a]++,in[b]++;
if(in[a]>=3||in[b]>=3)can[cur]=1;
p[fp(a)]=cur;
p[fp(b)]=cur;
mx[cur]=w;
}
int lca(int a,int b){
if(lv[a]<lv[b])swap(a,b);
for(int i=19;i>=0;i--)if(lv[pa[i][a]]>=lv[b])a=pa[i][a];
if(a==b)return a;
for(int i=19;i>=0;i--)if(pa[i][a]!=pa[i][b])a=pa[i][a],b=pa[i][b];
return pa[0][a];
}
void dfs(int u,int p){
//cerr<<u<<" "<<mx[u]<<"\n";
lv[u]=lv[p]+1;
pa[0][u]=p;
for(int i=1;i<20;i++)pa[i][u]=pa[i-1][pa[i-1][u]];
for(auto x:adj[u]){
dfs(x.first,u);
}
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
n=N,m=M;
vector<pair<int,pair<int,int>>>edge;
for(int i=0;i<M;i++){
edge.push_back({W[i],{++U[i],++V[i]}});
}
sort(edge.begin(),edge.end());
cur=N;
for(int i=1;i<=2*N;i++)p[i]=i;
for(auto x:edge){
un(x.second.first,x.second.second,x.first);
}
dfs(cur,cur);
/*cerr<<"can:\n";
for(int i=1;i<=2*n-1;i++)cerr<<can[i]<<" ";
cerr<<"\n";*/
}
int getMinimumFuelCapacity(int X, int Y) {
X++,Y++;
int rt=lca(X,Y);
//cerr<<"QR:"<<X<<" "<<Y<<":"<<rt<<"\n";
if(can[rt])return mx[rt];
for(int i=19;i>=0;i--){
if(!can[pa[i][rt]])rt=pa[i][rt];
}
if(rt==cur)return -1;
return mx[pa[0][rt]];
}
