#include "swap.h"
#include <bits/stdc++.h>
#define MAX 201010
using namespace std;
typedef pair<int, int> pii;
pii edges[MAX];
int W[MAX];
vector<pii> p[MAX];
vector<pii> numv[MAX];
vector<pii> nume[MAX];
int deg[MAX];
int val[MAX];
int rnk[MAX];
int N, M;
int find(int v, int t) {
int loc = lower_bound(p[v].begin(), p[v].end(), pii(t + 1, -2)) - p[v].begin();
loc--;
return p[v][loc].second;
}
int getnumv(int v, int t) {
int loc = lower_bound(numv[v].begin(), numv[v].end(), pii(t + 1, -2)) - numv[v].begin();
loc--;
return numv[v][loc].second;
}
int getnume(int v, int t) {
int loc = lower_bound(nume[v].begin(), nume[v].end(), pii(t + 1, -2)) - nume[v].begin();
loc--;
return nume[v][loc].second;
}
void uni(int u, int v, int t) {
deg[u]++;
deg[v]++;
int mx = max(deg[u], deg[v]);
u = find(u, t);
v = find(v, t);
if (rnk[u] < rnk[v]) swap(u, v);
if (u == v) nume[v].emplace_back(t, nume[v].back().second + 1);
else {
if (rnk[u] == rnk[v]) rnk[u]++;
p[v].emplace_back(t, u);
numv[u].emplace_back(t, numv[v].back().second + numv[u].back().second);
nume[u].emplace_back(t, nume[v].back().second + nume[u].back().second + 1);
if (val[v] <= t) val[u] = min(val[u], t);
}
if (mx > 2) val[u] = min(val[u], t);
}
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> _W) {
N = _N;
M = _M;
int i;
vector<int> v;
for (i = 0; i < M; i++) v.push_back(i);
sort(v.begin(), v.end(), [&](int i, int j) {return _W[i] < _W[j]; });
i = 0;
for (auto x : v) {
edges[i] = pii(U[x], V[x]);
W[i] = _W[x];
i++;
}
for (i = 0; i < N; i++) p[i].emplace_back(-1, i), nume[i].emplace_back(-1, 0), numv[i].emplace_back(-1, 1), val[i] = M;
for (i = 0; i < M; i++) {
uni(edges[i].first, edges[i].second, i);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int l, r;
l = -1, r = M;
while (r - l > 1) {
int m = (l + r + 2) >> 1;
m--;
int x = find(X, m);
int y = find(Y, m);
if (x != y) {
l = m;
continue;
}
if (getnumv(x, m) <= getnume(x, m)) r = m;
else if (val[x] <= m) r = m;
else l = m;
}
if (r == M) return -1;
return W[r];
}
