#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
vector<array<int, 3> > edges(MAXN * 2);
int DP[20][MAXN * 3];
int depth[MAXN * 3];
vector<int> g[MAXN * 3];
struct ufds {
bool isLine;
pair<int, int> endpoints;
int parent, value;
ufds(int x) {
isLine = true;
endpoints = {x, x};
parent = x;
value = 1e9;
}
} *Node[MAXN * 3];
int Find(int x) {
if(Node[x]->parent == x) {
return x;
}
return Node[x]->parent = Find(Node[x]->parent);
}
void Unite(int a, int b, int new_idx, int cur_val) {
int original_a = a, original_b = b;
a = Find(a);
b = Find(b);
Node[a]->parent = new_idx;
Node[b]->parent = new_idx;
g[new_idx].push_back(a);
g[new_idx].push_back(b);
Node[new_idx]->value = cur_val;
DP[0][a] = new_idx;
DP[0][b] = new_idx;
if(a == b || !Node[a]->isLine || !Node[b]->isLine) {
Node[new_idx]->isLine = false;
Node[new_idx]->endpoints = {-1, -1};
}
else {
//cout << "a = " << a << ", b = " << b << "\n";
//cout << "A Line = " << Node[a]->endpoints.first << ", " << Node[a]->endpoints.second << "\n";
//cout << "B Line = " << Node[b]->endpoints.first << ", " << Node[b]->endpoints.second << "\n";
if(Node[a]->endpoints.first != original_a) {
swap(Node[a]->endpoints.first, Node[a]->endpoints.second);
}
if(Node[b]->endpoints.first != original_b) {
swap(Node[b]->endpoints.first, Node[b]->endpoints.second);
}
if(original_a == Node[a]->endpoints.first && original_b == Node[b]->endpoints.first) {
Node[new_idx]->isLine = true;
Node[new_idx]->endpoints = {Node[a]->endpoints.second, Node[b]->endpoints.second};
}
else {
Node[new_idx]->isLine = false;
Node[new_idx]->endpoints = {-1, -1};
}
}
}
bool cmp(array<int, 3> a, array<int, 3> b) {
return a[2] < b[2];
}
void dfs(int node, int dep) {
depth[node] = dep;
for(int i = 0; i < g[node].size(); i++) {
dfs(g[node][i], dep + 1);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
auto begin = std::chrono::high_resolution_clock::now();
for(int i = 0; i < 20; i++) {
for(int j = 0; j < MAXN * 3; j++) {
DP[i][j] = -1;
}
}
for(int i = 0; i < M; i++) {
edges[i] = {U[i], V[i], W[i]};
}
sort(edges.begin(), edges.begin() + M, cmp);
int cur_new = N;
for(int i = 0; i < MAXN * 3; i++) {
Node[i] = new ufds(i);
}
for(int i = 0; i < M; i++) {
//cout << Find(edges[i][0]) << " " << Find(edges[i][1]) << "\n";
int x = Find(edges[i][0]), y = Find(edges[i][1]);
//cout << "x = " << x << ", Node[x] is a line? " << Node[x]->isLine << "\n";
if(x != y || Node[x]->isLine == true) {
//cout << "Uniting edge: (" << edges[i][0] << ", " << edges[i][1] << ", " << edges[i][2] << ")\n";
Unite(edges[i][0], edges[i][1], cur_new++, edges[i][2]);
}
}
assert(cur_new <= MAXN * 3);
for(int i = 1; i < 20; i++) {
for(int j = 0; j < cur_new; j++) {
if(DP[i - 1][j] != -1) {
DP[i][j] = DP[i - 1][DP[i - 1][j]];
}
else {
DP[i][j] = -1;
}
}
}
dfs(cur_new - 1, 0);
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << elapsed.count() * 1e-9 << "\n";
if(elapsed.count() * 1e-9 > 2.0) {
assert(false);
}
}
int lca(int X, int Y) {
if(depth[X] < depth[Y]) {
swap(X, Y);
}
int diff = depth[X] - depth[Y];
for(int i = 19; i >= 0; i--) {
if(diff >= (1 << i)) {
diff -= (1 << i);
X = DP[i][X];
}
}
assert(depth[X] == depth[Y]);
for(int i = 19; i >= 0; i--) {
if(DP[i][X] != -1) {
if(DP[i][X] != DP[i][Y] || Node[DP[i][X]]->isLine) {
X = DP[i][X];
Y = DP[i][Y];
}
}
if(DP[i][X] != -1 && (DP[i][X] != DP[i][Y] && Node[DP[i][X]]->isLine)) {
X = DP[i][X];
Y = DP[i][Y];
}
}
if(DP[0][X] == -1) {
return -1;
}
X = DP[0][X];
Y = DP[0][Y];
if(X != Y || Node[X]->isLine) {
return -1;
}
return Node[X]->value;
}
int getMinimumFuelCapacity(int X, int Y) {
return lca(X, Y);
}
