#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll,ll> prll;
#define fi first
#define se second
#define sz size
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) ((x).begin()), ((x).end())
#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)
inline void maxa (ll &a, ll b) { if (a<b) a=b; }
inline void mina (ll &a, ll b) { if (a>b) a=b; }
#define mxN (100'010ll)
#define mxM (200'010ll)
#define lgN (17ll)
#define INF (LLONG_MAX>>3ll)
ll n, m;
struct PUF
{
vcll par, ct, dt, wei, deg;
vcb comp;
inline void bd()
{
par.resize(mxN);
ct.resize(mxN);
dt.resize(mxN);
wei.resize(mxN);
deg.resize(mxN);
comp.resize(mxN);
ll u;
f0r(u,1,n)
{
par[u]=u;
ct[u]=dt[u]=INF;
wei[u]=1;
deg[u]=0;
comp[u]=0;
}
}
ll find (ll u)
{
if (par[u]==u) return u;
return find(par[u]);
}
void unite (ll u, ll v, ll w)
{
u=find(u);
v=find(v);
if (wei[u]<wei[v]) swap(u,v);
if (u==v)
{
mina(ct[u],w);
mina(ct[v],w);
comp[u]=comp[v]=1;
return;
}
par[v]=u;
dt[v]=w;
wei[u]+=wei[v];
comp[u] = comp[v] = (++deg[u]>=3 or ++deg[v]>=3 or comp[u] or comp[v]);
if (comp[u])
{
mina(ct[u],w);
mina(ct[v],w);
}
}
}puf;
struct edge { ll u, v, w; };
bool cmp (edge &a, edge &b) { return a.w<b.w; }
vc<edge> edges;
ll root;
vcll dep(mxN);
vc<vcll> gr(mxN);
vc<vc<prll>> lift(lgN+2, vc<prll>(mxN));
inline void dfs (ll u=0, ll d=0)
{
dep[u]=d;
for (ll v:gr[u]) dfs(v,d+1);
}
inline void bd_tree()
{
ll k, u;
f0r(u,1,n) if (puf.par[u]==u) root=u;
puf.par[root]=0;
gr[0].pb(root);
f0r(u,1,n)gr[puf.par[u]].pb(u);
f0r(u,1,n) lift[0][u] = {puf.par[u], puf.dt[u]};
f0r(k,1,lgN) f0r(u,1,n)
{
ll p=lift[k-1][u].fi;
lift[k][u].fi = lift[k-1][p].fi;
lift[k][u].se = max(lift[k-1][u].se, lift[k-1][p].se);
}
dfs();
}
void init(int N1, int M1, vc<int> U1, vc<int> V1, vc<int> W1)
{
n=N1; m=M1;
puf.bd();
ll i;
f0r(i,0,m-1)
{
edge e;
e.u=U1[i]+1;
e.v=V1[i]+1;
e.w=W1[i];
edges.pb(e);
}
sort(all(edges), cmp);
for (edge &e:edges) puf.unite(e.u, e.v, e.w);
bd_tree();
}
ll X, Y;
inline prll mpq (ll u, ll v)
{
ll mx=-1, k;
if (dep[u]<dep[v]) swap(u,v);
r0f(k,lgN,0)
{
ll p=lift[k][u].fi, w=lift[k][u].se;
if (dep[p]>=dep[v])
{
u=p;
maxa(mx,w);
}
}
if (u==v) return {mx,u};
r0f(k,lgN,0)
{
ll p1=lift[k][u].fi, w1=lift[k][u].se;
ll p2=lift[k][v].fi, w2=lift[k][v].se;
if (p1!=p2)
{
u=p1; v=p2;
maxa(mx,max(w1,w2));
}
}
maxa(mx, max(lift[0][u].se, lift[0][v].se));
return {mx,lift[0][u].fi};
}
inline ll find_ct (ll u)
{
while (puf.par[u]!=u and !puf.comp[u]) u=puf.par[u];
return puf.ct[u];
}
int getMinimumFuelCapacity(int X1, int Y1)
{
X=X1+1; Y=Y1+1;
prll res=mpq(X,Y);
return puf.comp[root] ? max(res.fi, find_ct(res.se)) : -1;
}
