#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
namespace{
const ll maxn = 1e5+5;
const ll mxpw = 18;
const int inf = (1<<30);
int par[maxn][mxpw];
int bei[maxn][3][mxpw]; // node, edge, tree edge weight
vector<pii> g[maxn];
vector<pii> tre[maxn];
vector<int> dep(maxn);
vector<int> dg(maxn);
int kpar[maxn], jpar[maxn];
}
int kfin(int a){
if (kpar[a] == a) return a;
return kpar[a] = kfin(kpar[a]);
}
bool kmerg(int a, int b, int w){
int ia = a, ib = b;
a = kfin(a); b = kfin(b);
if (a == b) return 0;
kpar[a] = b;
tre[ia].pb({ib, w});
tre[ib].pb({ia, w});
dg[ia]++;
if (dg[ia] >= 3 && bei[ia][0][0] == inf){
bei[ia][0][0] = w;
}
dg[ib]++;
if (dg[ib] >= 3 && bei[ib][0][0] == inf){
bei[ib][0][0] = w;
}
return 1;
}
int jfin(int a){
if (jpar[a] == a) return a;
return jpar[a] = jfin(jpar[a]);
}
void jmerg(int a, int b){
a = jfin(a); b = jfin(b);
if (a == b) return;
if (dep[a] > dep[b]) jpar[a] = b;
else jpar[b] = a;
}
void dfs(int u, int pre){
par[u][0] = pre;
if (pre == -1) par[u][0] = u;
REP1(i, mxpw-1){
par[u][i] = par[par[u][i-1]][i-1];
}
for (auto [v, w]:tre[u]){
if (v == pre) continue;
bei[v][2][0] = w;
dep[v] = dep[u]+1;
dfs(v, u);
}
}
void dfs2(int u, int pre){
// bei all initialized
REP1(bb, mxpw-1){
bei[u][0][bb] = min(bei[u][0][bb-1], bei[par[u][bb-1]][0][bb-1]);
bei[u][1][bb] = min(bei[u][1][bb-1], bei[par[u][bb-1]][1][bb-1]);
bei[u][2][bb] = max(bei[u][2][bb-1], bei[par[u][bb-1]][2][bb-1]);
}
for (auto [v, w]:tre[u]){
if (v == pre) continue;
dfs2(v, u);
}
}
int lca(int a, int b){
if (dep[a] < dep[b]) swap(a, b);
int gol = dep[a] - dep[b];
REP(i, mxpw) if ((gol>>i)&1) a = par[a][i];
if (a == b) return a;
RREP(i, mxpw){
if (par[a][i] != par[b][i]){
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
REP(i, n) REP(j, 2) bei[i][j][0] = inf;
REP(i, n) kpar[i] = jpar[i] = i;
vector<pii> ee;
REP(i, m){
ee.pb({W[i], i});
}
sort(ALL(ee));
vector<int> nontre;
for (auto [w, id]:ee){
if (kmerg(U[id], V[id], w)){
}
else{
nontre.pb(id);
}
}
dfs(0, -1);
for (auto id:nontre){
int w = W[id];
int u = jfin(U[id]), v = jfin(V[id]);
int goldep = dep[lca(u, v)];
while(dep[u] > dep[goldep]){
bei[u][1][0] = w;
jmerg(u, par[u][0]);
u = jfin(u);
}
while(dep[v] > dep[goldep]){
bei[v][1][0] = w;
jmerg(v, par[v][0]);
v = jfin(v);
}
}
dfs2(0, -1);
}
int getjumps(int a, int b, int wh){
if (dep[a] < dep[b]) swap(a, b);
int pp = lca(a, b);
int gol = dep[a] - dep[pp] + (wh == 0);
int ret = inf;
if (wh == 2) ret = 0;
REP(i, mxpw){
if ((gol>>i)&1){
if (wh == 2) ret = max(ret, bei[a][2][i]);
else ret = min(ret, bei[a][wh][i]);
a = par[a][i];
}
}
gol = dep[b] - dep[pp] + (wh == 0);
REP(i, mxpw){
if ((gol>>i)&1){
if (wh == 2) ret = max(ret, bei[b][2][i]);
else ret = min(ret, bei[b][wh][i]);
b = par[b][i];
}
}
return ret;
}
int getMinimumFuelCapacity(int X, int Y) {
int rt = max(getjumps(X, Y, 2), min(getjumps(X, Y, 0), getjumps(X, Y, 1)));
if (rt == inf) return -1;
return rt;
}
