#include "swap.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <iostream>
#define mp make_pair
#define pb push_back
#define CHECK_BIT(var, pos) (var & (1 << (pos)))
using namespace std;
typedef pair<int, int> pi;
const int INF = 1e9 + 2;
const int MAXUP = 19;
struct DSU {
int size;
vector<int> rep;
vector<int> rank;
void init(int N) {
size = N;
rank.assign(size, 0);
rep.resize(size);
for (int i = 0; i < N; i++) {
rep[i] = i;
}
}
int find(int a) {
if (a == rep[a]) {
return a;
}
rep[a] = find(rep[a]);
return rep[a];
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return false;
}
if (rank[a] < rank[b]) {
swap(a, b);
}
if (rank[a] == rank[b]) {
rank[a]++;
}
rep[b] = a;
return true;
}
};
struct State {
// We have convered the range [node, ancestor]
int ancestor;
int res;
};
struct Edge {
int u, v, w;
};
bool operator < (Edge a, Edge b) {
return a.w < b.w;
}
int N, M;
DSU graph;
bool cycle;
int super = 0;
// Total edge weights of any single node
vector<vector<int>> total;
// Referring to the graph OUTSIDE MST
vector<vector<pi>> adj_list;
// Referring to the MST
vector<pi> par;
vector<vector<pi>> kids;
vector<int> dep;
vector<vector<State>> ancestor;
vector<Edge> edges;
vector<int> split;
State merge(State a, State b) {
State c;
c.ancestor = b.ancestor;
c.res = max(a.res, b.res);
return c;
}
void dfs(int node, int p, int wp) {
par[node] = mp(p, wp);
if (node) {
kids[node].erase(find(kids[node].begin(), kids[node].end(), mp(p, wp)));
}
for (auto [kid, w] : kids[node]) {
dep[kid] = dep[node] + 1;
dfs(kid, node, w);
}
tie(p, wp) = par[node];
ancestor[0][node].ancestor = p;
ancestor[0][node].res = wp;
}
State jump(State a, int b) {
for (int up = MAXUP - 1; up >= 0; up--) {
if (CHECK_BIT(b, up)) {
a = merge(a, ancestor[up][a.ancestor]);
}
}
return a;
}
// Best outside edge in the path a--b and maximum edge in the path a--b
pi lca(int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
State a = {u, 0};
State b = {v, 0};
a = jump(a, dep[u] - dep[v]);
if (a.ancestor == b.ancestor) {
return {a.ancestor, a.res};
}
for (int up = MAXUP - 1; up >= 0; up--) {
State n_a = merge(a, ancestor[up][a.ancestor]);
State n_b = merge(b, ancestor[up][b.ancestor]);
if (n_a.ancestor != n_b.ancestor) {
a = n_a;
b = n_b;
}
}
int l = ancestor[0][a.ancestor].ancestor;
a = merge(a, ancestor[0][a.ancestor]);
b = merge(b, ancestor[0][b.ancestor]);
return {l, max(a.res, b.res)};
}
void calculate(int node) {
split[node] = total[node][2];
for (auto [kid, w] : kids[node]) {
calculate(kid);
split[node] = min(split[node], max(split[kid], w));
}
for (auto [u, w] : adj_list[node]) {
int l, p;
tie(l, p) = lca(u, node);
split[node] = min(split[node], max(p, w));
}
}
void propagate(int node, int v) {
split[node] = min(split[node], v);
for (auto [kid, w] : kids[node]) {
propagate(kid, max(split[node], w));
}
}
void precalculate(void) {
for (int up = 1; up < MAXUP; up++) {
for (int i = 0; i < N; i++) {
ancestor[up][i] = merge(ancestor[up - 1][i], ancestor[up - 1][ancestor[up - 1][i].ancestor]);
}
}
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
N = n;
M = m;
adj_list.resize(N);
par.resize(N);
split.resize(N);
kids.resize(N);
graph.init(N);
dep.assign(N, 0);
ancestor.resize(MAXUP, vector<State>(N));
total.resize(N);
for (int i = 0; i < M; i++) {
edges.pb({U[i], V[i], W[i]});
}
sort(edges.begin(), edges.end());
super = 0;
for (auto [u, v, w] : edges) {
if (graph.unite(u, v)) {
kids[u].pb(mp(v, w));
kids[v].pb(mp(u, w));
}
else {
adj_list[u].pb(mp(v, w));
adj_list[v].pb(mp(u, w));
}
total[u].pb(w);
total[v].pb(w);
super = max(super, w);
}
cycle = true;
for (int i = 0; i < N; i++) {
cycle = (cycle) && (adj_list[i].size() + kids[i].size() == 2);
}
if (cycle) {
return;
}
for (int i = 0; i < N; i++) {
// Push back "infinite" weight edge (if at any point we use any of these, ans is -1)
total[i].pb(INF);
total[i].pb(INF);
sort(total[i].begin(), total[i].end());
}
dfs(0, 0, INF);
precalculate();
calculate(0);
propagate(0, INF);
}
int getMinimumFuelCapacity(int X, int Y) {
if (cycle) {
return super;
}
int l, ans;
tie(l, ans) = lca(X, Y);
ans = max(ans, split[X]);
if (ans == INF) {
return -1;
}
else {
return ans;
}
}
