#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
vector <int> adj[N];
vector <int> s[N];
int max_e[N][20];
int ok_e[N][20];
int anc[N][20];
int ok_v[N];
int par[N];
int deg[N];
int fr[N];
int to[N];
int w[N];
int h[N];
int n,m;
bool notmst[N];
int getpar(int u) {
return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}
bool join(int u, int v) {
u = getpar(u);
v = getpar(v);
if (u == v)
return false;
if (par[u] > par[v])
swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
int getlca(int u, int v) {
if (h[u] > h[v])
swap(u, v);
for (int i = 19; i >= 0; i--)
if (h[v] - bit(i) >= h[u])
v = anc[v][i];
if (u == v)
return v;
for (int i = 19; i >= 0; i--) if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
return anc[v][0];
}
void dfs(int u, int p = -1) {
anc[u][0] = p;
for (int i : adj[u]) {
int v = fr[i] ^ to[i] ^ u;
if (v == p)
continue;
h[v] = h[u] + 1;
max_e[v][0] = w[i];
dfs(v, u);
}
}
void build() {
vector <int> ind(m, 0);
iota(ALL(ind), 0);
sort(ALL(ind), [](int i, int j) {
return w[i] < w[j];
});
for (int i = 0; i < n; i++)
par[i] = -1;
for (int i : ind) {
if (join(fr[i], to[i])) {
adj[fr[i]].push_back(i);
adj[to[i]].push_back(i);
} else
notmst[i] = true;
}
dfs(0);
for (int j = 1; j < 20; j++)
for (int i = 0; i < n; i++) {
int p = anc[i][j - 1];
anc[i][j] = (p < 0) ? -1 : (anc[p][j - 1]);
}
for (int i = 0; i < n; i++)
ok_v[i] = ok_e[i][0] = 2 * oo;
max_e[0][0] = 2 * oo;
for (int i = 0; i < n; i++) {
par[i] = -1;
s[i].push_back(i);
}
for (int it : ind) {
deg[fr[it]]++;
deg[to[it]]++;
int mx = max(deg[fr[it]], deg[to[it]]);
int u = getpar(fr[it]);
int v = getpar(to[it]);
if (s[u].size() > s[v].size())
swap(u, v);
if (min(s[u].size(), s[v].size()) == 0)
mx = 3;
if (mx == 3) {
for (int x : s[u])
ok_v[x] = w[it];
s[u].clear();
for (int x : s[v])
ok_v[x] = w[it];
s[v].clear();
}
if (u != v) {
for (int x : s[u])
s[v].push_back(x);
s[u].clear();
par[v] += par[u];
par[u] = v;
}
}
for (int i = 0; i < n; i++)
par[i] = -1;
for (int it : ind) if (notmst[it]) {
int u = fr[it];
int v = to[it];
int p = getlca(u, v);
for (int i = getpar(u); h[i] > h[p]; i = getpar(i)) {
ok_e[i][0] = w[it];
par[i] = anc[i][0];
}
for (int i = getpar(v); h[i] > h[p]; i = getpar(i)) {
ok_e[i][0] = w[it];
par[i] = anc[i][0];
}
}
for (int j = 1; j < 20; j++)
for (int i = 0; i < n; i++) {
int p = anc[i][j - 1];
if (p < 0) {
max_e[i][j] = ok_e[i][j] = 2 * oo;
} else {
ok_e[i][j] = min(ok_e[i][j - 1], ok_e[p][j - 1]);
max_e[i][j] = max(max_e[i][j - 1], max_e[p][j - 1]);
}
}
}
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++) {
fr[i] = U[i];
to[i] = V[i];
w[i] = W[i];
}
build();
}
int getmax(int u, int p) {
int res = 0;
for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
maxi(res, max_e[u][i]);
u = anc[u][i];
}
return res;
}
int minEdge(int u, int p) {
int res = 2 * oo;
for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
mini(res, ok_e[u][i]);
u = anc[u][i];
}
return res;
}
int getMinimumFuelCapacity(int u, int v) {
if (h[u] > h[v])
swap(u, v);
int p = getlca(u, v);
int res = max(getmax(u, p), getmax(v, p));
int ed = min(minEdge(u, p), minEdge(v, p));
int vt = min(ok_v[u], ok_v[v]);
// cerr << u << " " << v << " " << vt << " " << ed << "\n";
maxi(res, min(vt, ed));
if (res == 2 * oo)
res = -1;
return res;
}
#include "swap.h"
//#include "grader.cpp"
