#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;
// Best edge in the range, ignoring:
// a) Edges from kids to parents in the range
// b) All edges of bottom node
int best;
// Maximum edge in the path from node to parent
int mx;
};
struct Edge {
int u, v, w;
};
bool operator < (Edge a, Edge b) {
return a.w < b.w;
}
int N, M;
DSU graph;
// 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;
// Best path from node to par using edge outside the MST
vector<int> nicepath;
State merge(State a, State b) {
State c;
c.ancestor = b.ancestor;
c.best = min(a.best, b.best);
c.mx = max(a.mx, b.mx);
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;
if (wp != total[p][0] && par[p].second != total[p][0]) {
ancestor[0][node].best = total[p][0];
}
else if (wp != total[p][1] && par[p].second != total[p][1]) {
ancestor[0][node].best = total[p][1];
}
else {
ancestor[0][node].best = total[p][2];
}
ancestor[0][node].mx = wp;
}
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]);
}
}
}
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
tuple<int, int, int> lca(int u, int v) {
if (dep[u] < dep[v]) {
swap(u, v);
}
State a = {u, INF, 0};
State b = {v , INF, 0};
a = jump(a, dep[u] - dep[v]);
if (a.ancestor == b.ancestor) {
return {a.ancestor, a.best, a.mx};
}
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;
int best = min(a.best, b.best);
int e1 = par[a.ancestor].second;
int e2 = par[b.ancestor].second;
if (e1 > e2) {
swap(e1, e2);
}
if (total[l][0] == e1) {
if (total[l][1] == e2) {
best = min(best, total[l][2]);
}
else {
best = min(best, total[l][1]);
}
}
else {
best = min(best, total[l][0]);
}
a = merge(a, ancestor[0][a.ancestor]);
b = merge(b, ancestor[0][b.ancestor]);
return {l, best, max(a.mx, b.mx)};
}
int findpath(int i) {
int ans = INF;
for (auto [v, w] : adj_list[i]) {
int l, out, in;
tie(l, out, in) = lca(i, v);
ans = min(ans, max(in, w));
}
return ans;
}
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);
kids.resize(N);
graph.init(N);
nicepath.resize(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());
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);
}
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);
sort(total[i].begin(), total[i].end());
}
par[0] = mp(0, 0);
dep[0] = 0;
dfs(0, 0, INF);
precalculate();
for (int i = 0; i < N; i++) {
nicepath[i] = findpath(i);
}
}
int wait(int X, int e) {
int e1 = total[X][0];
int e2 = total[X][1];
if (e1 == e) {
e1 = total[X][2];
}
else if (e2 == e) {
e2 = total[X][2];
}
return max(e1, e2);
}
int getMinimumFuelCapacity(int X, int Y) {
int l, out, in;
tie(l, out, in) = lca(X, Y);
int ans = in;
// Find alternatives;
int alt = min(nicepath[Y], wait(Y, par[Y].second));
if (Y == l) {
swap(X, Y);
}
if (X != l) {
alt = min(alt, out);
alt = min(alt, min(nicepath[X], wait(X, par[X].second)));
}
else {
State s = {Y, INF, 0};
s = jump(s, dep[Y] - dep[X] - 1);
l = s.ancestor;
out = s.best;
in = s.mx;
int e = par[l].second;
alt = min(alt, out);
alt = min(alt, min(nicepath[X], wait(X, e)));
}
ans = max(ans, alt);
if (ans == INF) {
return -1;
}
else {
return ans;
}
}
