#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
struct DSU {
vector<int> par;
DSU (int n) {
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int get (int x) {
if (par[x] == x) return x;
else return par[x] = get(par[x]);
}
bool combine (int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
par[x] = y;
return true;
}
bool sameCC (int x, int y) {
return get(x) == get(y);
}
};
struct Edge {
int u, v, w;
int move (int x) {
if (u == x) return v;
else return u;
}
};
bool cmpEdge (const Edge& a, const Edge& b) {
return a.w < b.w;
}
const int INF = (int)1e18;
int numV, numE;
vector<Edge> edges;
vector<vector<int>> adj;
vector<vector<int>> mst;
vector<int> SP;
vector<int> depth;
vector<vector<int>> jump, jumpMax;
void dfs (int node, int par) {
for (int iEdge : mst[node]) {
Edge edgeOn = edges[iEdge];
int child = edgeOn.move(node), weight = edgeOn.w;
if (child == par);
jump[child][0] = node;
jumpMax[child][0] = weight;
depth[child] = depth[node] + 1;
dfs(child, node);
}
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
numV = N, numE = M;
edges.resize(numE);
adj.resize(numV);
mst.resize(numV);
SP.assign(numV, INF);
jump.assign(numV, vector<int>(32));
jumpMax.assign(numV, vector<int>(32, 0));
depth.resize(numV);
for (int i = 0; i < numE; i++) {
edges[i] = Edge{U[i], V[i], W[i]};
}
sort(edges.begin(), edges.end(), cmpEdge);
for (int i = 0; i < numE; i++) {
Edge edgeOn = edges[i];
adj[edgeOn.u].push_back(i);
adj[edgeOn.v].push_back(i);
}
DSU dsu(numV);
for (int i = 0; i < numE; i++) {
Edge edgeOn = edges[i];
if (!dsu.sameCC(edgeOn.u, edgeOn.v)) {
mst[edgeOn.u].push_back(i);
mst[edgeOn.v].push_back(i);
dsu.combine(edgeOn.u, edgeOn.v);
}
else {
SP[edgeOn.u] = min(SP[edgeOn.u], edgeOn.w);
SP[edgeOn.v] = min(SP[edgeOn.v], edgeOn.w);
}
}
for (int i = 0; i < numV; i++) {
if ((int)adj[i].size() >= 3) {
SP[i] = min(SP[i], edges[adj[i][2]].w);
}
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> PQ;
for (int i = 0; i < numV; i++) {
PQ.push({SP[i], i});
}
while (!PQ.empty()) {
pair<int,int> on = PQ.top();
PQ.pop();
int nodeOn = on.s, valOn = on.f;
if (SP[nodeOn] < valOn) {
continue;
}
for (int iEdge : adj[nodeOn]) {
Edge edgeNxt = edges[iEdge];
int nodeNxt = edgeNxt.move(nodeOn), weight = edgeNxt.w;
if (SP[nodeNxt] > max(SP[nodeOn], weight)) {
SP[nodeNxt] = max(SP[nodeOn], weight);
PQ.push({SP[nodeNxt], nodeNxt});
}
}
}
depth[0] = 0;
dfs(0, -1);
for (int len = 1; len < 32; len++) {
for (int i = 0; i < numV; i++) {
jump[i][len] = jump[jump[i][len-1]][len-1];
jumpMax[i][len] = max(jumpMax[i][len-1], jumpMax[jump[i][len-1]][len-1]);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = max(ans, min(SP[X], SP[Y]));
int lo = X, hi = Y;
if (lo == hi) {
if (ans == INF) return -1;
else return ans;
}
if (depth[hi] > depth[lo]) {
swap(lo, hi);
}
for (int len = 31; len >= 0; len--) {
if (depth[jump[lo][len]] >= depth[hi]) {
ans = max(ans, jumpMax[lo][len]);
lo = jump[lo][len];
}
}
assert(depth[lo] == depth[hi]);
if (lo == hi) {
if (ans == INF) return -1;
else return ans;
}
for (int len = 31; len >= 0; len--) {
if (jump[lo][len] != jump[hi][len]) {
ans = max({ans, jumpMax[lo][len], jumpMax[hi][len]});
lo = jump[lo][len];
hi = jump[hi][len];
}
}
assert(jump[lo][0] == jump[hi][0]);
ans = max({ans, jumpMax[lo][0], jumpMax[hi][0]});
if (ans == INF) return -1;
else return ans;
}
