#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9+1;
const ll inf = 2e18;
const ll mod = 998244353;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
const int mxn = 1e5+5;
mt19937 _rand(time(NULL));
#include "swap.h"
vector<pii> g[mxn];
int n, m;
int sparse[mxn][20];
int mxw[mxn][20];
int depth[mxn];
int _c[mxn];
int dp[mxn];
void dfs(int u, int p, int val){
sparse[u][0] = p;
fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
mxw[u][0] = val;
fr(i, 1, 20) mxw[u][i] = max(mxw[u][i-1], mxw[sparse[u][i-1]][i-1]);
dp[u] = _c[u];
for(auto e : g[u]){
if(e.st == p) continue;
depth[e.st] = depth[u] + 1;
dfs(e.st, u, e.nd);
dp[u] = min(dp[u], max(dp[e.st], e.nd));
}
}
int dpup[mxn];
void dfs2(int u, int p, int carry){
carry = min(carry, _c[u]);
dpup[u] = carry;
int id = p;
int min1 = carry;
int min2 = i_inf;
for(auto e : g[u]){
if(e.st == p) continue;
int cand1 = max(dp[e.st], e.nd);
if(cand1 < min1){
min2 = min1;
id = e.st;
min1 = cand1;
}else if(cand1 < min2){
min2 = cand1;
}
}
for(auto e : g[u]){
if(e.st == p) continue;
if(e.st == id){
dfs2(e.st, u, max(e.nd, min2));
}
else{
dfs2(e.st, u, max(e.nd, min1));
}
}
}
int lca(int a, int b){
int mind = min(depth[a], depth[b]);
for(int i = 19; i >= 0; i --){
if(depth[a] - (1<<i) >= mind) a = sparse[a][i];
if(depth[b] - (1<<i) >= mind) b = sparse[b][i];
}
if(a == b) return a;
for(int i = 19; i >= 0; i --){
if(sparse[a][i] != sparse[b][i]){
a = sparse[a][i];
b = sparse[b][i];
}
}
return sparse[a][0];
}
int cost(int u, int p){
int ret = 0;
for(int i = 19; i >= 0; i --){
if(depth[u] - (1<<i) >= depth[p]){
ret = max(ret, mxw[u][i]);
u = sparse[u][i];
}
}
return ret;
}
int link[mxn];
int sz[mxn];
bool used[200005];
int findx(int x){
if(x == link[x]) return x;
link[x] = findx(link[x]);
return link[x];
}
void unite(int a, int b, int wi, int i){
int u = a, v = b;
a = findx(a);
b = findx(b);
if(a == b) return;
used[i] = true;
if(sz[a] < sz[b]) swap(a, b);
link[b] = a;
sz[a] += sz[b];
g[u].pb({v, wi});
g[v].pb({u, wi});
}
vector<pii> G[mxn];
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
n = N, m = M;
vector<pii> S;
fr(i, 0, m){
S.pb({W[i], i});
}
sort(all(S));
fr(i, 0, n){
link[i] = i;
sz[i] = 1;
}
for(auto edge : S){
int u = U[edge.nd];
int v = V[edge.nd];
unite(u, v, edge.st, edge.nd);
}
fr(i, 0, m){
G[U[i]].pb({W[i], i});
G[V[i]].pb({W[i], i});
}
fr(i, 0, n){
sort(all(g[i]), [](const pii A, const pii B){
return A.nd < B.nd;
});
sort(all(G[i]));
}
fr(i, 0, n){
_c[i] = i_inf;
if((int)g[i].size() >= 3) _c[i] = g[i][2].nd;
for(auto u : G[i]){
if(used[u.nd]) continue;
_c[i] = min(_c[i], u.st);
break;
}
}
dfs(0, 0, i_inf);
dfs2(0, 0, i_inf);
}
int line = 0;
int getMinimumFuelCapacity(int X, int Y){
int k = lca(X, Y);
int c = max(min(dp[k], dpup[k]), max(cost(X, k), cost(Y, k)));
if(c == i_inf) c = -1;
return c;
}
