#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 20;
const int inf = 1e9 + 20;
bool flag[maxN];
vector<pair<int, int>> adj[maxN];
int deg[maxN];
int depth[maxN];
pair<int, int> par[maxN];
int T[maxN];
vector<pair<int, int>> tree;
int ROOT;
bool sub1, sub2;
int N, M, lim;
bool f1, f2;
int root(int u) {
if (par[u].first == -1) {
return u;
}
return root(par[u].first);
}
void update(int u, int v, int w) {
deg[u]++;
deg[v]++;
sub2 &= (deg[u] <= 2);
sub2 &= (deg[v] <= 2);
int ru = root(u);
int rv = root(v);
if (ru == rv) {
T[ru] = min(T[ru], w);
return;
}
if (depth[ru] > depth[rv]) {
swap(ru, rv);
}
T[rv] = min(T[rv], max(T[ru], w));
if (deg[u] >= 3 || deg[v] >= 3) {
T[rv] = min(T[rv], w);
}
par[ru] = {rv, w};
tree.push_back({ru, rv});
if (depth[ru] == depth[rv]) {
depth[rv]++;
}
}
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
N = _N;
M = _M;
sub1 = (M == (N - 1));
sub2 = true;
vector<pair<int, pair<int, int>>> edges(M);
for (int i = 0; i < M; i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
edges[i] = make_pair(W[i], make_pair(U[i], V[i]));
}
for (int i = 0; i < N; i++) {
T[i] = inf;
par[i] = {-1, -1};
}
sort(edges.begin(), edges.end());
for (auto e: edges) {
int w = e.first;
int u = e.second.first;
int v = e.second.second;
update(u, v, w);
}
for (int i = 0; i < N; i++) {
depth[i] = -1;
}
ROOT = root(0);
depth[ROOT] = 1;
reverse(tree.begin(), tree.end());
for (auto e: tree) {
int u = e.first;
int v = e.second;
assert(depth[v] != -1);
depth[u] = depth[v] + 1;
}
for (int i = 0; i < N; i++) {
assert(depth[i] != -1);
if (i != ROOT) {
assert(par[i].first != -1);
}
}
}
void dfs(int u) {
flag[u] = true;
int cnt = 0;
for (auto e: adj[u]) {
int v = e.first;
int w = e.second;
if (w <= lim) {
cnt++;
}
if (w <= lim && !flag[v]) {
dfs(v);
}
}
f1 &= (cnt <= 2);
f2 |= (cnt <= 1);
}
int getMinimumFuelCapacity(int u, int v) {
int tmp_u = u;
int tmp_v = v;
int res1 = 0;
int res2 = inf;
if (depth[u] < depth[v]) {
swap(u, v);
}
while (depth[u] != depth[v]) {
res1 = max(res1, par[u].second);
u = par[u].first;
assert(u != -1);
}
while (u != v) {
res1 = max(res1, par[u].second);
u = par[u].first;
res1 = max(res1, par[v].second);
v = par[v].first;
assert(u != -1);
assert(v != -1);
}
u = tmp_u;
int cur = 0;
int res7 = inf;
while (u != -1) {
res7 = min(res7, max(T[u], cur));
cur = max(cur, par[u].second);
u = par[u].first;
}
v = tmp_v;
cur = 0;
int res8 = inf;
while (v != -1) {
res8 = min(res8, max(T[v], cur));
cur = max(cur, par[v].second);
v = par[v].first;
}
int res = max(res1, min(res7, res8));
if (res == inf) {
return -1;
}
else {
return res;
}
}
