/*
Find minimum spanning tree
Answer is the max of these three things
- Path max from u to v
- Minimum of third adjacent minimums from u to v
*/
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
const int INF = 2e9;
struct DSU{
int p[MAXN], sz[MAXN];
void init() {
for (int i = 0; i < MAXN; i++) {
p[i] = i;
sz[i] = 1;
}
}
int find_set(int u) {
vector<int> chain = {u};
while (p[chain.back()] != chain.back()) {
chain.push_back(p[chain.back()]);
}
int ret = chain.back();
for (int i : chain) p[i] = ret;
return ret;
}
bool merge_set(int u, int v) {
u = find_set(u); v = find_set(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
return true;
}
} dsu;
vector<pair<int, int>> edge[MAXN];
int depth[MAXN], p[20][MAXN], pc[20][MAXN], p3[20][MAXN];
void dfs(int u) {
for (auto [v, w] : edge[u]) {
if (depth[v] != -1) continue;
depth[v] = depth[u] + 1;
p[0][v] = u;
pc[0][v] = w;
dfs(v);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
dsu.init();
tuple<int, int, int> edge_list[M];
for (int i = 0; i < M; i++) {
edge_list[i] = make_tuple(W[i], U[i], V[i]);
}
sort(edge_list, edge_list+M);
vector<int> adj_weight[N];
for (int i = 0; i < M; i++) {
int w, u, v;
tie(w, u, v) = edge_list[i];
if (dsu.merge_set(u, v)) {
edge[u].emplace_back(v, w);
edge[v].emplace_back(u, w);
}
adj_weight[u].push_back(w);
adj_weight[v].push_back(w);
}
fill(depth, depth+N, -1);
depth[0] = p[0][0] = pc[0][0] = 0;
dfs(0);
for (int i = 0; i < N; i++) {
p3[0][i] = (adj_weight[i].size() >= 3 ? adj_weight[i][2] : INF);
}
for (int j = 1; j <= 19; j++) {
for (int i = 0; i < N; i++) {
p[j][i] = p[j-1][p[j-1][i]];
pc[j][i] = max(pc[j-1][i], pc[j-1][p[j-1][i]]);
p3[j][i] = min(p3[j-1][i], p3[j-1][p[j-1][i]]);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int ret1 = 0;
int ret2 = INF;
if (depth[X] < depth[Y]) swap(X, Y);
int delta_depth = depth[X] - depth[Y];
for (int j = 19; j >= 0; j--) {
if (delta_depth&(1<<j)) {
ret1 = max(ret1, pc[j][X]);
ret2 = min(ret2, p3[j][X]);
X = p[j][X];
}
}
if (X == Y) {
ret2 = min(ret2, p3[0][X]);
return max(ret1, ret2) >= INF ? -1 : max(ret1, ret2);
}
for (int j = 19; j >= 0; j--) {
if (p[j][X] != p[j][Y]) {
ret1 = max({ret1, pc[j][X], pc[j][Y]});
ret2 = min({ret2, p3[j][X], p3[j][Y]});
X = p[j][X];
Y = p[j][Y];
}
}
ret1 = max({ret1, pc[0][X], pc[0][Y]});
ret2 = min({ret2, p3[0][X], p3[0][Y], p3[0][p[0][X]]});
return max(ret1, ret2) >= INF ? -1 : max(ret1, ret2);
}
