#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 2e5 + 1;
const int lg = 25;
vector <int> ad [maxn];
int deg[maxn];
int dad [maxn];
int val [maxn];
vector <bool> line (maxn, 1);
vector <int> cmp[maxn];
vector <int> depth (maxn);
int dg[maxn];
int up[maxn][lg];
bool bad1 = 1, bad2 = 1;
void dfs (int u) {
for (auto v: cmp[u]) {
depth[v] = depth[u] + 1;
up[v][0] = u;
for (int i = 1; i < lg; i++){
up[v][i] = up[up[v][i-1]][i-1];
}
dfs(v);
}
}
int lca (int x, int y) {
if (depth[x] < depth[y]) {
swap(x, y);
}
int k = depth[x] - depth[y];
for (int i = 0; i < lg; i++){
if (k & (1 << i)) {
x = up[x][i];
}
}
if (x == y) return x;
for (int i = lg - 1; i >= 0; i--) {
if (up[x][i] != up[y][i]) {
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
int get_dad (int x) {
return (dad[x] == x ? x: get_dad(dad[x]));
}
void merge (int a, int b) {
a = get_dad(a);
b = get_dad(b);
if (a == b) return;
if (!line[a]) line[b] = 0;
dad[a] = b;
cmp[b].push_back(a);
}
void find (int u, vector <int> &nodes) {
nodes.push_back(u);
for (int v: cmp[u]) {
find(v, nodes);
}
}
struct edg {
int x,y,cost;
};
bool comp (edg &a, edg &b) {
return a.cost < b.cost;
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
vector <edg> eg;
for (int i = 0; i < maxn; i++){
dad[i] = i;
for (int j = 0; j < lg; j++){
up[i][j] = maxn - 1;
}
}
for (int i = 0; i < m; i++){
dg[u[i]]++;
dg[v[i]]++;
eg.push_back({u[i], v[i], w[i]});
}
for (int i = 0; i < n; i++){
if (dg[i] > 2) bad1 = 0;
if (dg[i] != 2) bad2 = 0;
}
sort(eg.begin(), eg.end(), comp);
for (auto &[u,v,cost]: eg) {
// if (u == 1 && v == 4) break;
int p1 = get_dad(u);
int p2 = get_dad(v);
// cout << u << " " << v << " " << p1 << " " << p2 << " ";
if (p1 == p2) {
if (line[p1]) {
vector <int> nodes;
find(p1, nodes);
int node = ++extra;
for (int i: nodes) {
dad[i] = node;
cmp[node].push_back(i);
}
line[p1] = 0;
val[node] = cost;
}
}
else {
deg[u]++;
deg[v]++;
if (deg[u] >= 3 || deg[v] >= 3) {
int node = ++extra;
line[node] = 0;
merge(p1, node);
merge(p2, node);
val[node] = cost;
}
else merge(u,v);
}
}
// for (int i = 0; i < 15; i++){
// cout << i << " " << val[i] << "\n";
// }
// for (int i = 0; i < 15; i++){
// cout << i << ": ";
// for (int j: cmp[i]) {
// cout << j << " ";
// }
// cout << "\n";
// }
// for (int i = 0; i < 15; i++){
// cout << i << " " << dad[i] << "\n";
// }
dfs(extra);
}
int getMinimumFuelCapacity(int x, int y) {
if (bad1 || bad2) return -1;
return val[lca(x,y)];
}
