//Challenge: Accepted
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct edge{
int u, v, w;
edge(){u = v = w = 0;}
edge(int a, int b, int c){u = a, v = b, w = c;}
};
struct DSU{
int par[maxn], deg[maxn];
bool mark[maxn];
pii leaf[maxn];
void init(int n) {
for (int i = 0;i < n;i++) par[i] = i, deg[i] = 0, mark[i] = 0, leaf[i] = {i, 0};
}
int find(int a) {
return a == par[a] ? a : (par[a] = find(par[a]));
}
void Union(int a, int b) {
int pa = find(a), pb = find(b);
deg[a]++, deg[b]++;
if (deg[a] >= 3 || deg[b] >= 3 || mark[pa]) mark[pb] = 1;
if (deg[a] == 1 && deg[b] == 1) {
leaf[pb] = {a, b};
} else {
if (pa == pb && (leaf[pa] == make_pair(a, b) || leaf[pa] == make_pair(b, a))) mark[pb] = 1;
if (pa != pb) {
pii p;
if (deg[leaf[pa].ff] == 1) p.ff = leaf[pa].ff;
else p.ff = leaf[pa].ss;
if (deg[leaf[pb].ff] == 1) p.ss = leaf[pb].ff;
else p.ss = leaf[pb].ss;
leaf[pb] = p;
}
}
par[pa] = pb;
}
} d;
vector<edge> ed;
int n, m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N, m = M;
for (int i = 0;i < m;i++) ed.push_back(edge(U[i], V[i], W[i]));
sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
}
int getMinimumFuelCapacity(int X, int Y) {
d.init(n);
int ret = -1;
for (int i = 0;i < m;i++) {
d.Union(ed[i].u, ed[i].v);
int v = d.find(X);
debug(v, d.leaf[v].ff, d.leaf[v].ss);
if (d.find(X) == d.find(Y) && d.mark[d.find(X)]) {
ret = ed[i].w;
break;
}
}
debug();
return ret;
}
