//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;}
};
vector<pii> ev[maxn]; //events
int valid[maxn];
struct DSU{
int par[maxn], deg[maxn], siz[maxn];
bool mark[maxn];
pii leaf[maxn];
int ti;
void init(int n) {
for (int i = 0;i < n;i++) {
ev[i].push_back({-1, i});
siz[i] = 1;
par[i] = i, deg[i] = 0, mark[i] = 0, leaf[i] = {i, 0};
valid[i] = 1<<30;
}
ti = 0;
}
int find(int a) {
if (a == par[a]) return a;
int ret = find(par[a]);
if (ret != par[a]) ev[a].push_back({ti, ret});
par[a] = ret;
return ret;
}
void Union(int a, int b) {
int pa = find(a), pb = find(b);
if (siz[pa] > siz[pb]) swap(pa, pb), swap(a, b);
deg[a]++, deg[b]++;
if (deg[a] >= 3 || deg[b] >= 3 || mark[pa]) {
valid[pb] = min(valid[pb], ti);
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))) {
valid[pb] = min(valid[pb], ti);
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;
}
}
if (pa != pb) {
siz[pb] += siz[pa];
ev[pa].push_back({ti, pb});
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;});
d.init(n);
for (int i = 0;i < m;i++) {
d.Union(ed[i].u, ed[i].v);
d.ti++;
}
}
int pfind(int a, int ti) {
int ind = upper_bound(ev[a].begin(), ev[a].end(), make_pair(ti, 1<<30)) - ev[a].begin() - 1;
if (ev[a][ind].ss == a) return a;
return pfind(ev[a][ind].ss, ti);
}
int getMinimumFuelCapacity(int X, int Y) {
int low = 0, up = m;
while (low < up - 1) {
int mid = (low + up) / 2;
int vx = pfind(X, mid), vy = pfind(Y, mid);
if (vx == vy && valid[vx] <= mid) up = mid;
else low = mid;
}
if (up == m) return -1;
else return ed[up].w;
}
