#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,M=2e5+50,lg=19;
int n,m;
vector<array<int,3>>grane;
//kruskal reconstruction tree
vector<int>E[N+M];
int par[N+M][lg+1],w[N+M],depth[N+M],root,nc;
bool ciklus[N+M];
void DFS(int u){
depth[u]=depth[par[u][0]]+1;
for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
for(auto i:E[u])DFS(i);
}
int LCA(int u,int v){
if(depth[u]<depth[v])swap(u,v);
for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}
int dsupar[N],deg[N],rep[N];
bool dsuciklus[N];
void Init(int n){
for(int i=0;i<=n;i++)dsupar[i]=rep[i]=i;
nc=n;
}
int FS(int u){if(dsupar[u]==u)return u;return dsupar[u]=FS(dsupar[u]);}
void US(int u,int v,int weight){
deg[u]++,deg[v]++;
bool mx=0;if(max(deg[u],deg[v])>=3)mx=1;
u=FS(u),v=FS(v);
nc++;
w[nc]=weight;
par[rep[u]][0]=par[rep[v]][0]=nc;
rep[v]=nc;
if(u==v){
ciklus[nc]=dsuciklus[u]=true;
return;
}
ciklus[nc]=dsuciklus[v]=max({dsuciklus[u],dsuciklus[v],mx});
dsupar[u]=v;
}
void init(int n1,int m1,vector<int>U,vector<int>V,vector<int>W){
n=n1,m=m1;
for(int i=0;i<m;i++)grane.pb({W[i],U[i]+1,V[i]+1});
sort(grane.begin(),grane.end());
Init(n);
for(auto [w,u,v]:grane) US(u,v,w);
//for(int i=1;i<=nc;i++) printf("%i: %i\n",i,par[i][0]);
root=++nc;
for(int i=1;i<nc;i++)if(par[i][0]==0)par[i][0]=root;
for(int i=1;i<=nc;i++) E[par[i][0]].pb(i);
DFS(root);
ciklus[0]=ciklus[root]=true;
w[0]=w[root]=-1;
}
int getMinimumFuelCapacity(int X,int Y){
X++,Y++;
int u=LCA(X,Y);
for(int i=lg;i>=0;i--){
if(!ciklus[par[u][i]])u=par[u][i];
}
if(!ciklus[u])u=par[u][0];
return w[u];
}
