#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e9 + 37;
vector<vector<int> > g;
struct Edge
{
int from, to, c;
Edge() { }
Edge(int u, int v, int w) : from(u), to(v), c(w) {
}
bool operator<(const Edge& other) const {
return c < other.c;
}
};
struct Node
{
bool is_line = true;
array<int, 2> endpoints;
int par, size, w;
Node(int u) : endpoints({u, u}), par(u), size(1), w(inf) {
}
};
vector<Node> dsu;
vector<Edge> edges;
int idx = -1;
int get_root(int v) { // currently slow
return (dsu[v].par == v ? v : dsu[v].par = get_root(dsu[v].par));
}
void merge(int u, int v, int c) {
int paru = get_root(u), parv = get_root(v);
if(paru == parv) {
dsu[paru].is_line = false;
dsu[paru].w = min(dsu[paru].w, c);
return;
}
if(dsu[paru].size > dsu[parv].size) {
swap(u, v);
swap(paru, parv);
}
int cur_node = dsu.size();
dsu.emplace_back(Node(cur_node));
if(find(dsu[paru].endpoints.begin(), dsu[paru].endpoints.end(), u) != dsu[paru].endpoints.end() and
find(dsu[parv].endpoints.begin(), dsu[parv].endpoints.end(), v) != dsu[parv].endpoints.end()) {
dsu[cur_node].endpoints = {dsu[paru].endpoints[dsu[paru].endpoints[0] == u], dsu[parv].endpoints[dsu[parv].endpoints[0] == v]};
}
else {
dsu[cur_node].endpoints = {-1, -1};
dsu[cur_node].is_line = false;
dsu[cur_node].w = min(dsu[cur_node].w, c);
}
g.emplace_back();
g[cur_node].push_back(paru);
g[cur_node].push_back(parv);
dsu[paru].par = dsu[parv].par = cur_node;
dsu[cur_node].size = dsu[paru].size + dsu[parv].size;
}
vector<vector<int> > fa;
vector<int> dep, closest_anc;
const int LOG = 20;
void depth_dfs(int v, int cur_close) {
if(dsu[v].w != inf)
cur_close = v;
closest_anc[v] = cur_close;
for(int to : g[v]) {
dep[to] = dep[v] + 1;
fa[to][0] = v;
depth_dfs(to, cur_close);
}
}
void init_lca(void) {
int n = dsu.size();
closest_anc.assign(n, -1);
fa.assign(n, vector<int>(LOG, -1));
dep.assign(n, -1);
for(int i = 0; i < n; ++i) {
if(dep[i] == -1) {
int v = get_root(i);
dep[v] = 0;
depth_dfs(v, -1);
}
}
for(int jump = 1; jump < LOG; ++jump) {
for(int i = 0; i < n; ++i) {
fa[i][jump] = (fa[i][jump - 1] == -1 ? -1 : fa[fa[i][jump - 1]][jump - 1]);
}
}
// for(int i = 0; i < n; ++i) {
// cout << i << " : ";
// for(int j = 0; j < 3; ++j)
// cout << fa[i][j] << ' ';
// cout << endl;
// }
}
int lca(int u, int v) {
if(dep[u] < dep[v]) {
swap(u, v);
}
int diff = dep[u] - dep[v];
// cout << u << ' ' << v << " Diff : " << diff << endl;
for(int jump = 0; jump < LOG; ++jump) {
if((1 << jump) & diff)
u = fa[u][jump];
}
assert(u != v);
assert(u != -1);
for(int jump = LOG - 1; jump >= 0; --jump) {
if(u == -1 or v == -1) {
// if(u == -1)
// cout << "u";
// if(v == -1)
// cout << "v";
// cout << endl;
assert(false);
}
if(fa[u][jump] != fa[v][jump]) {
u = fa[u][jump];
v = fa[v][jump];
assert(u != -1 and v != -1);
}
}
assert(u != v);
return closest_anc[fa[u][0]];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
g.assign(N, vector<int>());
edges.assign(M, Edge());
for(int i = 0; i < M; ++i) {
edges[i] = {U[i], V[i], W[i]};
}
sort(edges.begin(), edges.end());
for(int i = 0; i < N; ++i) {
dsu.emplace_back(Node(i));
}
for(const Edge& e : edges) {
merge(e.from, e.to, e.c);
}
init_lca();
}
int getMinimumFuelCapacity(int X, int Y) {
if(get_root(X) != get_root(Y)) {
return -1;
}
int anc = lca(X, Y);
if(anc == -1) {
return -1;
}
assert(dsu[anc].w != inf);
return dsu[anc].w;
}
