#include "swap.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 17;
const int INF = 2e9;
int n, m;
struct Sparse
{
int par[MAXLOG][MAXN];
int max[MAXLOG][MAXN];
int dep[MAXN];
void build(int p[], int e[], int d[])
{
for (int i = 1 ; i <= n ; ++i)
{
par[0][i] = p[i];
max[0][i] = e[i];
dep[i] = d[i];
}
for (int log = 1 ; (1 << log) <= n ; ++log)
{
for (int i = 1 ; i <= n ; ++i)
{
par[log][i] = par[log - 1][par[log - 1][i]];
max[log][i] = std::max(max[log - 1][i], max[log - 1][par[log - 1][i]]);
}
}
}
void equalize(int &u, int v, int &res)
{
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (dep[par[log][u]] >= dep[v])
{
res = std::max(res, max[log][u]);
u = par[log][u];
}
}
}
void calcLCA(int &u, int v, int &res)
{
if (u == v)
{
return;
}
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (par[log][u] != par[log][v])
{
res = std::max(res, max[log][u]);
res = std::max(res, max[log][v]);
u = par[log][u];
v = par[log][v];
}
}
res = std::max(res, max[0][v]);
res = std::max(res, max[0][u]);
u = par[0][u];
}
int findLCA(int u, int v)
{
int res = 0;
if (dep[u] < dep[v])
{
std::swap(u, v);
}
equalize(u, v, res);
calcLCA(u, v, res);
return u;
}
int findMAX(int u, int v)
{
int res = 0;
if (dep[u] < dep[v])
{
std::swap(u, v);
}
equalize(u, v, res);
calcLCA(u, v, res);
return res;
}
};
struct DSU
{
int par[MAXN];
int dep[MAXN];
void build()
{
std::iota(par + 1, par + 1 + n, 1);
std::fill(dep + 1, dep + 1 + n, 1);
}
int find(int node)
{
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void connect(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
{
return;
}
if (dep[u] > dep[v])
{
std::swap(u, v);
}
if (dep[u] == dep[v])
{
dep[v]++;
}
par[u] = v;
}
bool areConnected(int u, int v)
{
return find(u) == find(v);
}
};
struct Edge
{
int u, v;
int dist;
friend bool operator < (const Edge &a, const Edge &b)
{
return a.dist < b.dist;
}
};
int p[MAXN];
int e[MAXN];
int dep[MAXN];
int minD[MAXN];
bool vis[MAXN];
std::priority_queue <std::pair <int,int>> relax;
std::vector <std::pair <int,int>> g[MAXN];
std::vector <std::pair <int,int>> t[MAXN];
std::vector <Edge> edges;
Sparse sparse;
DSU dsu;
void buildDFS(int node, int par)
{
p[node] = par;
dep[node] = dep[par] + 1;
for (const auto &[u, d] : t[node])
{
if (u == par)
{
continue;
}
e[u] = d;
buildDFS(u, node);
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n = N; m = M;
for (int i = 0 ; i < M ; ++i)
{
U[i]++; V[i]++;
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
edges.push_back({U[i], V[i], W[i]});
}
std::fill(minD + 1, minD + 1 + n, INF);
for (int i = 1 ; i <= n ; ++i)
{
std::sort(g[i].begin(), g[i].end(), [&](auto x, auto y)
{
return x.second < y.second;
});
if (g[i].size() >= 3)
{
minD[i] = g[i][2].second;
}
}
dsu.build();
std::sort(edges.begin(), edges.end());
for (const auto &[u, v, d] : edges)
{
if (dsu.areConnected(u, v))
{
minD[u] = std::min(minD[u], d);
minD[v] = std::min(minD[v], d);
} else
{
t[u].emplace_back(v, d);
t[v].emplace_back(u, d);
dsu.connect(u, v);
}
}
buildDFS(1, 0);
sparse.build(p, e, dep);
for (int i = 1 ; i <= n ; ++i)
{
relax.push({-minD[i], i});
}
while (!relax.empty())
{
auto [dist, node] = relax.top();
relax.pop();
if (vis[node])
{
continue;
}
vis[node] = true;
for (const auto &[u, d] : t[node])
{
if (minD[u] > std::max(minD[node], d))
{
minD[u] = std::max(minD[node], d);
relax.push({-minD[u], u});
}
}
}
}
int getMinimumFuelCapacity(int x, int y)
{
x++; y++;
int res = sparse.findMAX(x, y);
res = std::max(res, minD[x]);
res = std::max(res, minD[y]);
if (res == INF) return -1;
return res;
}
