#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 100000;
static const int LOG = 17;
vector<pair<int,int>> adj[MAXN];
int up[MAXN][LOG];
int mx[MAXN][LOG];
int depth[MAXN];
int parent[MAXN];
int n_global;
struct Edge {
int u, v, w;
};
int find_set(int v) {
return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}
void dfs(int v, int p, int w) {
up[v][0] = p;
mx[v][0] = w;
for (int i = 1; i < LOG; i++) {
up[v][i] = up[ up[v][i-1] ][i-1];
mx[v][i] = max(mx[v][i-1], mx[ up[v][i-1] ][i-1]);
}
for (auto [to, wt] : adj[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs(to, v, wt);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n_global = N;
vector<Edge> edges;
for (int i = 0; i < M; i++) {
edges.push_back({U[i], V[i], W[i]});
}
for (int i = 0; i < N; i++) {
parent[i] = i;
adj[i].clear();
}
sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
return a.w < b.w;
});
// Build MST
for (auto &e : edges) {
int a = find_set(e.u);
int b = find_set(e.v);
if (a != b) {
parent[a] = b;
adj[e.u].push_back({e.v, e.w});
adj[e.v].push_back({e.u, e.w});
}
}
depth[0] = 0;
dfs(0, 0, 0);
}
int getMinimumFuelCapacity(int X, int Y) {
int u = X;
int v = Y;
int ans = 0;
if (depth[u] < depth[v]) swap(u, v);
// Lift u up
for (int i = LOG - 1; i >= 0; i--) {
if (depth[u] - (1 << i) >= depth[v]) {
ans = max(ans, mx[u][i]);
u = up[u][i];
}
}
if (u == v) return ans;
// Lift both
for (int i = LOG - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
ans = max(ans, mx[u][i]);
ans = max(ans, mx[v][i]);
u = up[u][i];
v = up[v][i];
}
}
// One step to LCA
ans = max(ans, mx[u][0]);
ans = max(ans, mx[v][0]);
return ans;
}
