#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct merging_dsu {
vector<int> parent, cnt_v, cnt_e, deg, max_deg, T;
vector<vector<int>> comp;
merging_dsu(int size) : parent(size), cnt_v(size, 1), cnt_e(size), deg(size), max_deg(size), T(size, INT_MAX), comp(size) {
iota(parent.begin(), parent.end(), 0);
for (int i = 0; i < size; i++) {
comp[i] = {i};
}
}
int get(int u) {
return parent[u] == u ? u : (parent[u] = get(parent[u]));
}
void unite(int u, int v, int w) {
int new_val = max(++deg[u], ++deg[v]);
u = get(u), v = get(v);
if (u != v) {
if (cnt_v[u] < cnt_v[v]) {
swap(u, v);
}
parent[v] = u;
cnt_v[u] += cnt_v[v];
cnt_e[u] += cnt_e[v];
max_deg[u] = max(max_deg[u], max_deg[v]);
for (int x : comp[v]) {
comp[u].push_back(x);
}
}
max_deg[u] = max(max_deg[u], new_val);
cnt_e[u]++;
if (cnt_e[u] >= cnt_v[u] || max_deg[u] > 2) {
for (int x : comp[u]) {
T[x] = w;
}
comp[u] = vector<int>();
}
}
};
struct dsu {
vector<int> parent, rank;
dsu(int size) : parent(size), rank(size, 1) {
iota(parent.begin(), parent.end(), 0);
}
int get(int u) {
return parent[u] == u ? u : (parent[u] = get(parent[u]));
}
bool unite(int u, int v) {
u = get(u), v = get(v);
if (u != v) {
if (rank[u] < rank[v]) {
swap(u, v);
}
parent[v] = u;
rank[u] += rank[v];
return true;
}
return false;
}
};
const int MAX_L = 20;
struct binary_lifting {
vector<vector<array<int, 2>>> graph;
vector<vector<int>> up, dp;
vector<int> depth;
binary_lifting() {}
binary_lifting(vector<vector<array<int, 2>>> _graph) : graph(_graph) {
int N = (int)graph.size();
depth = vector<int>(N);
up = vector<vector<int>>(N, vector<int>(MAX_L));
dp = vector<vector<int>>(N, vector<int>(MAX_L, INT_MIN));
DFS(0, 0);
}
void DFS(int u, int p) {
up[u][0] = p;
for (int i = 1; i < MAX_L; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
dp[u][i] = max(dp[u][i - 1], dp[up[u][i - 1]][i - 1]);
}
for (auto [v, w] : graph[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dp[v][0] = w;
DFS(v, u);
}
}
}
int query(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
int ans = INT_MIN;
for (int i = MAX_L - 1; i >= 0; i--) {
if (depth[u] - (1 << i) >= depth[v]) {
ans = max(ans, dp[u][i]);
u = up[u][i];
}
}
if (u == v) {
return ans;
}
for (int i = MAX_L - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
ans = max({ans, dp[u][i], dp[v][i]});
u = up[u][i];
v = up[v][i];
}
}
return max({ans, dp[u][0], dp[v][0]});
}
};
binary_lifting BL;
vector<int> T;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
vector<vector<array<int, 2>>> graph(N);
vector<array<int, 3>> edges;
for (int i = 0; i < M; i++) {
edges.push_back({W[i], U[i], V[i]});
}
sort(edges.begin(), edges.end());
dsu sets(N);
merging_dsu D(N);
for (auto [W, U, V] : edges) {
D.unite(U, V, W);
if (sets.unite(U, V)) {
graph[U].push_back({V, W});
graph[V].push_back({U, W});
}
}
T = D.T;
BL = binary_lifting(graph);
}
int getMinimumFuelCapacity(int X, int Y) {
int value = max(T[X], BL.query(X, Y));
return value == INT_MAX ? -1 : value;
}
