#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> ans, dep, p, up, w, f;
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
vector<vector<int>> par;
constexpr int inf = 2e9;
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
N = n;
M = m;
p.resize(N + M);
iota(p.begin(), p.end(), 0);
vector<int> dif(N + M, -1), three(N + M), deg(N);
w.resize(N + M);
vector<vector<int>> ch(N + M);
auto unite = [&](int x, int y, int t) {
x = find(x);
y = find(y);
dif[t] = 1;
for (int z : set<int>{x, y}) {
three[t] |= three[z];
dif[t] += dif[z];
p[z] = t;
up[z] = t;
ch[t].push_back(z);
}
};
vector<tuple<int, int, int>> edges(M);
for (int i = 0; i < M; i++) {
edges[i] = {W[i], U[i], V[i]};
}
sort(edges.begin(), edges.end());
f.resize(N + M);
up.resize(N + M, -1);
for (int i = 0; i < M; i++) {
auto [z, x, y] = edges[i];
if (++deg[x] == 3) {
three[find(x)] = 1;
}
if (++deg[y] == 3) {
three[find(y)] = 1;
}
w[N + i] = z;
unite(x, y, N + i);
f[N + i] = three[N + i] == 1 || dif[N + i] >= 0;
}
}
int getMinimumFuelCapacity(int x, int y) {
if (find(x) != find(y)) {
return -1;
}
while (x != y) {
if (x < y) {
x = up[x];
} else {
y = up[y];
}
}
int ans = inf;
while (x != -1) {
if (f[x]) {
ans = min(ans, w[x]);
}
x = up[x];
}
if (ans == inf) {
ans = -1;
}
return ans;
}
