#include "swap.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
const int MAXN = 100013;
const int INF = 1e9 + 7;
int N, T;
int dsu[MAXN];
vpi edge[MAXN];
int t[MAXN];
pii corners[MAXN];
vi nodes[MAXN];
bitset<MAXN> ok;
int st[MAXN], ft[MAXN];
pii jump[20][MAXN];
bool insubt(int u, int v) //is v in the subtree of u?
{
return (u == N || (st[u] <= st[v] && st[v] <= ft[u]));
}
void dfs(int u, int p)
{
st[u] = T;
ft[u] = T;
T++;
for (auto e : edge[u])
{
int d = e.fi, v = e.se;
if (v == p) continue;
jump[0][v] = {u, d};
dfs(v, u);
ft[u] = ft[v];
}
}
int get(int u)
{
return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
void init(int n, int m, vi U, vi V, vi W)
{
N = n;
fill(t, t + N, INF);
vector<pair<int, pii> > edges(m);
FOR(i, 0, m)
{
edges[i] = {W[i], {U[i], V[i]}};
}
sort(ALL(edges));
FOR(i, 0, N)
{
dsu[i] = i;
nodes[i].PB(i);
corners[i] = {i, i};
}
for (auto e : edges)
{
int d = e.fi, u = e.se.fi, v = e.se.se;
int cu = get(u), cv = get(v);
if (cu == cv)
{
if (!ok[cu])
{
for (int w : nodes[cu]) t[w] = d;
ok[cu] = true;
}
//they're in the same component.
}
else
{
edge[u].PB({d, v});
edge[v].PB({d, u});
// cerr << "EDGE " << u << " <-> " << v << ' ' << d << endl;
if (SZ(nodes[cu]) < SZ(nodes[cv]))
{
swap(u, v);
swap(cu, cv);
}
//they're in different components.
bool bad = (!ok[cu] && !ok[cv]
&& (u == corners[cu].fi || u == corners[cu].se) && (v == corners[cv].fi || v == corners[cv].se));
if (bad) //update corners
{
pii corn = {corners[cu].fi ^ corners[cu].se ^ u, corners[cv].fi ^ corners[cv].se ^ v};
corners[cu] = corn;
}
else //mark anybody that needs to be marked.
{
if (!ok[cu])
{
for (int w : nodes[cu]) t[w] = d;
}
if (!ok[cv])
{
for (int w : nodes[cv]) t[w] = d;
}
ok[cu] = true;
}
nodes[cu].insert(nodes[cu].end(), ALL(nodes[cv]));
nodes[cv].clear();
dsu[cv] = cu;
}
}
jump[0][N] = {N, 0};
jump[0][0] = {N, 0};
dfs(0, N);
FOR(i, 1, 20)
{
FOR(j, 0, N + 1)
{
jump[i][j] = {jump[i - 1][jump[i - 1][j].fi].fi, max(jump[i - 1][j].se, jump[i - 1][jump[i - 1][j].fi].se)};
}
}
//now you want to be able to find longest edge on path u to v
}
int ask(int u, int v)
{
// cerr << "ASK " << u << ' ' << v << endl;
int res = 0;
FORD(i, 20, 0)
{
if (insubt(jump[i][u].fi, v)) continue;
ckmax(res, jump[i][u].se);
u = jump[i][u].fi;
}
if (!insubt(u, v))
{
ckmax(res, jump[0][u].se);
}
FORD(i, 20, 0)
{
if (insubt(jump[i][v].fi, u)) continue;
ckmax(res, jump[i][v].se);
v = jump[i][v].fi;
}
if (!insubt(v, u))
{
ckmax(res, jump[0][v].se);
}
return res;
}
int getMinimumFuelCapacity(int u, int v)
{
// cerr << "ASK " << ask(u, v) << endl;
int res = max(ask(u, v), max(t[u], t[v]));
if (res == INF) res = -1;
return res;
}
