#include "swap.h"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
typedef pair<int, int> pi;
typedef pair<int, pi> pp;
const int inf = 1 << 30;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
vector<pi> p, now;//pa, _t
vector<int> r, t;//rank
map<pi, pi> mp;//[ver, _t] : [l, r]
int find(int i) {
return p[i].first == i ? i : find(p[i].first);
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
p.clear(), now.clear(), r.clear(), mp.clear();
for (int i = 0; i < N; ++i) {
p.emplace_back(i, inf);
now.emplace_back(i, i);
r.push_back(0);
t.push_back(inf);
}
vector<pp> e;
for (int i = 0; i < M; ++i) e.emplace_back(W[i], pi(U[i], V[i]));
sort(all(e));
for (pp i : e) {
int x = find(i.second.first), y = find(i.second.second);
if (x == y) {
if (t[x] == inf)
t[x] = i.first, mp[{x, t[x]}] = now[x] = {-1, -1};
}
else {
if ((i.second.first != now[x].first && i.second.first != now[x].second) || (i.second.second != now[y].first && i.second.second != now[y].second)) {
now[x] = now[y] = {-1, -1};
t[x] = min(t[x], i.first);
t[y] = min(t[y], i.first);
}
else
now[x] = now[y] = pi(now[x].first ^ now[x].second ^ i.second.first, now[y].first ^ now[y].second ^ i.second.second);
if (r[x] < r[y]) swap(x, y);
else if (r[x] == r[y]) ++r[x];
p[y] = {x, i.first};
mp[{x, i.first}] = now[x];
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = 0;
while (X != Y) {
ans = min(p[X].second, p[Y].second);
while (p[X].second <= ans) X = p[X].first;
while (p[Y].second <= ans) Y = p[Y].first;
}
while (p[X].first != X && t[X] == inf) X = p[X].first;
return t[X] == inf ? -1 : max(ans, t[X]);
}
