#include <bits/stdc++.h>
#include "swap.h"
// #include "grader.cpp"
using namespace std;
#define ff first
#define ss second
#define pii pair<int, int>
vector<int> p, W, H;
vector<bool> swp;
vector<vector<int>> E, sp;
int fnd(int x) {
return p[x] = (x == p[x] ? x : fnd(p[x]));
}
void dfs(int x) {
for (auto i : E[x]) {
H[i] = H[x] + 1;
dfs(i);
}
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
vector<pair<int, pii>> edg;
for (int i = 0; i < m; i++)
edg.push_back({w[i], {u[i], v[i]}});
sort(edg.begin(), edg.end());
E.assign(n + m, {});
swp.assign(n + m, false);
sp.assign(n + m, vector<int>(20, -1));
p = W = vector<int>(n + m, 0);
iota(p.begin(), p.end(), 0);
int ind = n;
vector<int> cnt(n);
for (auto [w, i] : edg) {
int x = fnd(i.ff), y = fnd(i.ss);
cnt[i.ff]++; cnt[i.ss]++;
E[ind].push_back(x);
if (x != y) E[ind].push_back(y);
p[x] = p[y] = sp[x][0] = sp[y][0] = ind;
W[ind] = w;
swp[ind] = (x == y || swp[x] || swp[y] || 2 < max(cnt[i.ff], cnt[i.ss]));
ind++;
}
for (int i = 1; i < 20; i++) {
for (int j = 0; j < n + m; j++)
if (~sp[j][i - 1]) sp[j][i] = sp[sp[j][i - 1]][i - 1];
}
H.assign(n + m, 0);
dfs(ind - 1);
}
int getMinimumFuelCapacity(int s, int t) {
if (H[s] < H[t]) swap(s, t);
for (int i = 19; i >= 0; i--)
if (H[s] - (1 << i) >= H[t]) s = sp[s][i];
for (int i = 19; i >= 0; i--) {
if (sp[s][i] != sp[t][i]) {
s = sp[s][i]; t = sp[t][i];
}
}
s = sp[s][0];
if (swp[s]) return W[s];
for (int i = 19; i >= 0; i--) {
if (~sp[s][i] && !swp[sp[s][i]]) s = sp[s][i];
}
return (!~sp[s][0] ? -1 : W[sp[s][0]]);
}
