#include "swap.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <numeric>
using namespace std;
namespace {
const int INF = 2000000007;
struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}
};
int N_global, M_global;
int TOT = 0;
int LOGN = 0;
int ROOT = -1;
vector<Edge> edges;
// DSU on original vertices/components
vector<int> dsu, dsu_sz;
vector<int> comp_sz, comp_edges, comp_bad;
vector<int> rep; // representative node in reconstruction tree
vector<int> degv; // current degree in graph formed by processed edges
// Reconstruction tree
vector<vector<int>> tree;
vector<int> parent0;
vector<int> depthv;
vector<int> birth; // weight when this component node is created
vector<int> good; // earliest weight when this component becomes "non-path"
vector<int> answerNode; // answer for pairs whose LCA is this node
// LCA
vector<vector<int>> up;
int find_set(int v) {
if (dsu[v] == v) return v;
return dsu[v] = find_set(dsu[v]);
}
int union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a == b) return a;
if (dsu_sz[a] < dsu_sz[b]) swap(a, b);
dsu[b] = a;
dsu_sz[a] += dsu_sz[b];
return a;
}
inline bool is_non_path_component(int root) {
// Connected component is NOT a path iff:
// - there exists a vertex with degree >= 3 OR
// - number of edges >= number of vertices (there is a cycle)
return (comp_bad[root] > 0 || comp_edges[root] >= comp_sz[root]);
}
int lca(int a, int b) {
if (depthv[a] < depthv[b]) swap(a, b);
int diff = depthv[a] - depthv[b];
for (int k = LOGN - 1; k >= 0; --k) {
if (diff & (1 << k)) a = up[k][a];
}
if (a == b) return a;
for (int k = LOGN - 1; k >= 0; --k) {
if (up[k][a] != -1 && up[k][a] != up[k][b]) {
a = up[k][a];
b = up[k][b];
}
}
return parent0[a];
}
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
N_global = N;
M_global = M;
edges.clear();
edges.reserve(M);
for (int i = 0; i < M; ++i) {
edges.push_back({U[i], V[i], W[i]});
}
sort(edges.begin(), edges.end());
// Reconstruction tree has at most 2*N - 1 nodes
int MAXT = 2 * N + 5;
dsu.resize(N);
dsu_sz.assign(N, 1);
comp_sz.assign(N, 1);
comp_edges.assign(N, 0);
comp_bad.assign(N, 0);
rep.resize(N);
degv.assign(N, 0);
iota(dsu.begin(), dsu.end(), 0);
tree.assign(MAXT, {});
parent0.assign(MAXT, -1);
depthv.assign(MAXT, 0);
birth.assign(MAXT, -INF);
good.assign(MAXT, INF);
answerNode.assign(MAXT, INF);
// Leaves [0..N-1] correspond to original vertices
TOT = N;
for (int i = 0; i < N; ++i) {
rep[i] = i;
}
for (const auto& e : edges) {
int u = e.u, v = e.v, w = e.w;
int ru = find_set(u);
int rv = find_set(v);
bool incUToBad = false, incVToBad = false;
++degv[u];
if (degv[u] == 3) incUToBad = true;
++degv[v];
if (degv[v] == 3) incVToBad = true;
if (ru == rv) {
// Internal edge within one connected component
comp_edges[ru]++;
if (incUToBad) comp_bad[ru]++;
if (incVToBad) comp_bad[ru]++;
int node = rep[ru];
if (good[node] == INF && is_non_path_component(ru)) {
good[node] = w;
}
} else {
// Merge two components; create new node in reconstruction tree
int node = TOT++;
birth[node] = w;
int left = rep[ru];
int right = rep[rv];
tree[node].push_back(left);
tree[node].push_back(right);
parent0[left] = node;
parent0[right] = node;
int szA = comp_sz[ru], szB = comp_sz[rv];
int edA = comp_edges[ru], edB = comp_edges[rv];
int bdA = comp_bad[ru], bdB = comp_bad[rv];
int newRoot = union_sets(ru, rv);
comp_sz[newRoot] = szA + szB;
comp_edges[newRoot] = edA + edB + 1;
comp_bad[newRoot] = bdA + bdB + (int)incUToBad + (int)incVToBad;
rep[newRoot] = node;
if (is_non_path_component(newRoot)) {
good[node] = w;
}
}
}
ROOT = rep[find_set(0)];
// Propagate answerNode from root downward:
// If a component itself becomes non-path at time good[v], answer is good[v].
// Otherwise answer is inherited from the first ancestor that becomes non-path.
queue<int> q;
q.push(ROOT);
answerNode[ROOT] = good[ROOT];
while (!q.empty()) {
int v = q.front();
q.pop();
for (int to : tree[v]) {
depthv[to] = depthv[v] + 1;
answerNode[to] = (good[to] != INF ? good[to] : answerNode[v]);
q.push(to);
}
}
// Build binary lifting table
LOGN = 1;
while ((1 << LOGN) <= TOT) ++LOGN;
up.assign(LOGN, vector<int>(TOT, -1));
for (int i = 0; i < TOT; ++i) up[0][i] = parent0[i];
for (int k = 1; k < LOGN; ++k) {
for (int i = 0; i < TOT; ++i) {
if (up[k - 1][i] != -1) {
up[k][i] = up[k - 1][up[k - 1][i]];
}
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int L = lca(X, Y);
int ans = answerNode[L];
return (ans >= INF ? -1 : ans);
}
