#include "swap.h"
#include <bits/stdc++.h>
#define INF 1000000003
#define MAX 200000
#define ll long long
using namespace std;
int n;
vector<vector<int>> v, up;
vector<ll> ans, go, de, pa;
int cur;
struct DSU{
vector<int> p, le, ri, ro;
int cmp;
void init(int n){
p.assign(n + 1, -1);
ro.assign(n + 1, 0), le.assign(n + 1, 0), ri.assign(n + 1, 0);
for (int i = 1; i <= n; i++) ro[i] = i, le[i] = i, ri[i] = i;
cmp = n;
}
int find(int x){
if (p[x] < 0) return x;
return p[x] = find(p[x]);
}
void merge(int a, int b, ll co){
int ora = a, orb = b;
a = find(a), b = find(b);
if (a == b){
if (go[ro[a]] == 0) go[ro[a]] = 1, ans[ro[a]] = co;
return;
}
cmp--;
if (p[a] > p[b]) swap(a, b), swap(ora, orb);
if (ora == le[a]) swap(le[a], ri[a]);
if (orb == ri[b]) swap(le[b], ri[b]);
go[cur] = max(go[ro[a]], go[ro[b]]);
if (ri[a] != ora || le[b] != orb) go[cur] = 1;
ri[a] = ri[b];
ans[cur] = co;
p[a] += p[b];
p[b] = a;
v[cur].push_back(ro[a]);
v[cur].push_back(ro[b]);
ro[a] = cur;
cur++;
}
};
void dfs(int x, int p){
//cout<<x<<"\n";
de[x] = de[p] + 1;
up[x][0] = p;
for (int i = 1; i < 20; i++){
up[x][i] = up[up[x][i - 1]][i - 1];
}
if (go[x] == 0) ans[x] = -1;
for (auto el : v[x]){
if (go[x] == 1 && go[el] == 0) ans[el] = ans[x], go[el] = 1;
dfs(el, x);
}
}
int dist(int x, int k){
for (int i = 0; i < 20; i++){
int val = (k & (1<<i));
if (val != 0){
x = up[x][i];
}
}
return x;
}
int lca(int a, int b){
if (de[a] > de[b]) swap(a, b);
b = dist(b, de[b] - de[a]);
if (a == b) return a;
for (int i = 19; i >= 0; i--){
if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
}
return up[a][0];
}
DSU ds;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
v.assign(2 * n + 1, vector<int>()), ans.assign(2 * n + 1, INF), go.assign(2 * n + 1, 0);
de.assign(2 * n + 1, 0), pa.assign(2 * n + 1, 0), cur = n + 1;
up.assign(2 * n + 1, vector<int>(20, 0));
vector<vector<int>> so;
for (int i = 0; i < M; i++){
so.push_back({W[i], U[i] + 1, V[i] + 1});
}
ds.init(n);
sort(so.begin(), so.end());
for (auto el : so){
ds.merge(el[1], el[2], el[0]);
}
for (int i = 1; i <= 2 * n - 1; i++){
/*cout<<go[i]<<" "<<i<<": ";
for (auto el : v[i]) cout<<el<<" ";
cout<<"\n";*/
}
dfs(cur - 1, 0);
}
int getMinimumFuelCapacity(int x, int y){
x++, y++;
return ans[lca(x, y)];
}
