#include<bits/stdc++.h>
#include "swap.h"
//#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int inf = 1e9 + 1;
const int N = 1e5;
const int L = 17;
int par[N];
vector<int> have[N];
int endps[N][2];
int path[N];
int edge[N];
int ind[N];
int sprc[L][N];
void cresprc(vector<int> &v) {
int n = sz(v);
for (int ind = 0; ind < n; ind++) {
sprc[0][ind] = edge[v[ind]];
}
for (int lvl = 1; lvl < L; lvl++) {
int len = (1 << lvl);
for (int i = 0; n - i >= len; i++) {
sprc[lvl][i] = max(sprc[lvl - 1][i], sprc[lvl - 1][i + (len >> 1)]);
}
}
}
int dist(int x, int y) {
if (x == y) {
return 0;
}
if (ind[x] > ind[y]) {
swap(x, y);
}
x = ind[x] + 1;
y = ind[y];
int len = y - x + 1;
int lg = __lg(len);
return max(sprc[lg][x], sprc[lg][y - (1 << lg) + 1]);
}
void unio(int u, int v, int w) {
int p1 = par[u], p2 = par[v];
if (p1 == p2) {
if (endps[p1][0] != -1) {
endps[p1][0] = -1;
endps[p1][1] = -1;
for (auto x : have[p1]) {
path[x] = w;
}
}
return;
}
if (sz(have[p1]) < sz(have[p2])) {
swap(p1, p2);
swap(u, v);
}
bool ipath = true;
if (endps[p1][0] == -1 || endps[p1][1] == -1 || endps[p2][0] == -1 || endps[p2][1] == -1) {
ipath = false;
}
else {
ipath = false;
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
if (endps[p1][x] == u && endps[p2][y] == v) {
int e1 = endps[p1][!x];
int e2 = endps[p2][!y];
endps[p1][0] = e1;
endps[p1][1] = e2;
ipath = true;
break;
}
}
if (ipath) {
break;
}
}
}
if (!ipath && endps[p1][0] != -1) {
for (auto x : have[p1]) {
path[x] = w;
}
endps[p1][0] = -1;
endps[p1][1] = -1;
}
if (!ipath && endps[p2][0] != -1) {
for (auto x : have[p2]) {
path[x] = w;
}
endps[p2][0] = -1;
endps[p2][1] = -1;
}
edge[have[p2][0]] = w;
for (auto x : have[p2]) {
have[p1].pb(x);
par[x] = p1;
}
have[p2].clear();
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
pair<int, int> edges[M];
for (int e = 0; e < M; e++) {
edges[e] = mp(W[e], e);
}
sort(edges + 0, edges + M);
for (int v = 0; v < N; v++) {
par[v] = v;
have[v].pb(v);
endps[v][0] = v;
endps[v][1] = v;
}
for (int eind = 0; eind < M; eind++) {
int e = edges[eind].se;
int u = U[e];
int v = V[e];
int w = W[e];
unio(u, v, w);
}
for (int v = 0; v < N - 1; v++) {
unio(v, v + 1, inf);
}
for (int v = 0; v < N; v++) {
if (!path[v]) {
path[v] = inf;
}
}
int p = par[0];
for (int i = 0; i < N; i++) {
ind[have[p][i]] = i;
}
cresprc(have[p]);
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = max(dist(X, Y), max(path[X], path[Y]));
if (ans == inf) {
return -1;
}
return ans;
}
