#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }
struct DSU { // Sorry UFDS
vector<int> p, s, degree;
vector<bool> swappable;
int components;
void init(int n) {
p = vector<int>(n);
iota(all(p), 0);
s = vector<int>(n, 1);
swappable = vector<bool>(n, 0);
degree = vector<int>(n, 0);
components = n;
}
int get(int x) {
return p[x] = (p[x] == x ? x : get(p[x]));
}
void unite(int a, int b) {
degree[a]++;
degree[b]++;
bool _swappable = 0;
if (degree[a] >= 3 || degree[b] >= 3) _swappable = 1;
a = get(a);
b = get(b);
if (a == b) {
swappable[a] = 1;
return;
}
if (s[a] > s[b]) swap(a, b);
p[a] = b;
s[b] += s[a];
swappable[b] = (swappable[a] | swappable[b] | _swappable);
components--;
}
bool same_set(int a, int b) {
return get(a) == get(b);
}
int size(int x) {
return s[get(x)];
}
bool is_swappable(int a, int b) {
return same_set(a, b) && swappable[get(a)] && swappable[get(b)];
}
};
int n, m;
vector<vector<pair<int, int>>> adj;
vector<pair<int, pair<int, int>>> edges;
int inf = 1e9 + 7;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
adj.resize(n);
for (int i = 0; i < m; i++) {
adj[U[i]].emplace_back(V[i], W[i]);
adj[V[i]].emplace_back(U[i], W[i]);
edges.emplace_back(W[i], make_pair(U[i], V[i]));
}
sort(all(edges));
}
int getMinimumFuelCapacity(int x, int y) {
int ptr = 0;
DSU dsu;
dsu.init(n);
// cout << pl(x) << pl(y) << endl;
while (!dsu.is_swappable(x, y) && ptr < m) {
// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;
// cout << pl(edges[ptr]) << endl;
dsu.unite(edges[ptr].second.first, edges[ptr].second.second);
ptr++;
}
// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;
if (!dsu.is_swappable(x, y)) return -1;
// if (ptr == m && !dsu.swappable[dsu) return -1;
return edges[ptr - 1].first;
}
