#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; } template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; } const int MAXN = 3e5 + 5, LG = 18; int deg[MAXN], lab[MAXN], n, curNode, lowOk[MAXN], up[MAXN][LG + 1], dep[MAXN]; bool ok[MAXN]; vector<int> g[MAXN]; array<int, 3> e[MAXN]; int find(int u) { return lab[u] < 0 ? u : lab[u] = find(lab[u]); } void join(int u, int v) { deg[u]++; deg[v]++; curNode++; if (deg[u] >= 3 || deg[v] >= 3) ok[curNode] = 1; u = find(u); v = find(v); if (ok[u] || ok[v] || u == v) ok[curNode] = 1; lab[curNode] += lab[u]; if (u != v) lab[curNode] += lab[v]; lab[u] = lab[v] = curNode; g[curNode].emplace_back(u); if (u != v) g[curNode].emplace_back(v); } void dfs(int u, int p, int lst) { if (ok[u]) lst = u; lowOk[u] = lst; up[u][0] = p; for (int i = 1; i <= LG; i++) up[u][i] = up[up[u][i - 1]][i - 1]; for (int v : g[u]) { if (v != p) { dep[v] = dep[u] + 1; dfs(v, u, lst); } } } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int need = dep[u] - dep[v]; for (int i = 0; i <= LG; i++) { if (need >> i & 1) { u = up[u][i]; } } if (u == v) return u; for (int i = LG; i >= 0; i--) { if (up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { for (int i = 0; i < M; i++) { e[i] = {W[i], U[i], V[i]}; } sort(e, e + M); memset(lab, -1, (N + M + 5) * sizeof(int)); curNode = N - 1; n = N; for (int i = 0; i < M; i++) { join(e[i][1], e[i][2]); } dfs(curNode, curNode, 0); } int getMinimumFuelCapacity(int X, int Y) { int l = lca(X, Y); if (lowOk[l] < n) return -1; return e[lowOk[l] - n][0]; }