#include "swap.h"
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
vector<vector<array<ll, 3> > > adj;
vector<vector<ll> > anc, ans, ans2;
vector<ll> w, dep, cost, cost2, dist, vis, comp;
ll n, m, LOG = 20;
array<ll, 3> jump(ll u, ll k) {
ll res1 = 0, res2 = 0;
for (ll pw = 0; pw < LOG; pw++)
if (k >> pw & 1)
res1 = max(res1, ans[pw][u]), res2 = max(res2, ans2[pw][u]), u = anc[pw][u];
return {u, res1, res2};
}
array<ll, 3> lca(ll u, ll v) {
if (dep[u] < dep[v])swap(u, v);
auto [nxt, res1, res2] = jump(u, max(0LL, dep[u] - dep[v] - 1));
if (anc[0][nxt] == v)return {anc[0][nxt], max(res1, cost[nxt]), max(res2, ans2[0][nxt])};
auto [nxt2, r1, r2] = jump(u, dep[u] - dep[v]);
u = nxt2, res1 = r1, res2 = r2;
bool enter = 0;
for (ll pw = LOG - 1; pw >= 0; pw--)
if (anc[pw][u] != anc[pw][v]) {
res1 = max({res1, ans[pw][u], ans[pw][v]});
res2 = max({res2, ans2[pw][u], ans2[pw][v]});
u = anc[pw][u], v = anc[pw][v];
enter = 1;
}
res1 = max({res1, cost[u], cost[v]});
res2 = max({res2, ans2[0][u], ans2[0][v]});
return {anc[0][u], res1, res2};
}
ll ay7aga = 0;
struct DSU {
ll connected;
vector<ll> par, sz;
stack<array<ll, 2> > st;
void init(ll n) {
par = sz = vector<ll>(n + 1, 0);
for (ll i = 1; i <= n; i++)
par[i] = i, sz[i] = 1;
connected = n;
}
ll findparent(ll u) {
if (par[u] == u)return u;
ll parent = findparent(par[u]);
//if not rollback, uncomment
//par[u] = parent;
return parent;
}
ll getsize(ll u) {
return sz[findparent(u)];
}
void unite(ll u, ll v) {
ll par1 = findparent(u), par2 = findparent(v);
st.push({-1, -1});
if (par1 == par2)
return;
if (sz[par1] > sz[par2])
swap(par1, par2);
st.pop();
st.push({connected, par1});
connected--;
sz[par2] += sz[par1];
par[par1] = par2;
}
void rollback() {
if (st.size()) {
auto x = st.top();
st.pop();
if (x[0] == -1)return;
connected = x[0];
par[x[1]] = x[1];
}
}
bool is_connected(ll u, ll v) {
return findparent(u) == findparent(v);
}
} dsu;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N, m = M;
dsu.init(n);
anc = ans = ans2 = vector<vector<ll> >(LOG, vector<ll>(n + 1));
adj = vector<vector<array<ll, 3> > >(n + 1);
dep = cost = cost2 = vector<ll>(n + 1, 0);
vis = vector<ll>(n + 1, 0);
dist = vector<ll>(n + 1, LLONG_MAX);
for (ll i = 0; i < m; i++) {
U[i]++, V[i]++;
adj[U[i]].push_back({V[i], W[i], i});
adj[V[i]].push_back({U[i], W[i], i});
w.push_back(W[i]);
dsu.unite(U[i], V[i]);
ay7aga = max(ay7aga, (ll) W[i]);
}
ll all = 0;
function<void(ll)> dfs = [&](ll u) {
if (vis[u])return;
comp.push_back(u);
vis[u] = 1;
for (auto [v, we, idx]: adj[u])
dfs(v), all++;
};
priority_queue<array<ll, 2>, vector<array<ll, 2> >, greater<> > pq;
for (ll i = 1; i <= n; i++) {
if (!vis[i]) {
comp.clear();
dfs(i);
for (ll x: comp)cost[i] = all / 2 > (comp.size() - 1);
}
}
while (!pq.empty()) {
auto [c, u] = pq.top();
pq.pop();
if (c > dist[u])continue;
// cout << u << ' ' << dist[u] << nl;
for (auto [v, we, idx]: adj[u])
if (max(we, c) < dist[v])
pq.push({dist[v] = max(we, c), v});
}
sort(all(w));
w.erase(unique(all(w)), w.end());
}
int getMinimumFuelCapacity(int x, int y) {
return (dsu.is_connected(x, y) and cost[x]? ay7aga : -1);
}
