#include "swap.h"
#include <cstring>
#include <utility>
#include <vector>
#include <algorithm>
const int INF = 0x3f3f3f3f;
struct dsu {
dsu *p;
int size;
bool over;
std::vector<int> v;
dsu() {
over = false;
p = 0;
size = 1;
}
dsu *find() {
if (p) return p = p->find();
return this;
}
};
const int N = 100000;
const int M = 200000;
const int LG = 17;
int in[N], out[N], f[LG][N], up[LG][N], fi[N], deg[N];
std::vector<std::pair<int, int> > g[N];
std::pair<int, std::pair<int, int> > e[M];
dsu d[N];
void update(std::vector<int> &v, int w)
{
while (!v.empty()) {
fi[v.back()] = w;
v.pop_back();
}
}
bool unite(dsu *a, dsu *b, int w)
{
a = a->find();
b = b->find();
if (a == b) return 0;
if (a->size < b->size) std::swap(a, b);
b->p = a;
a->size += b->size;
a->v.insert(a->v.end(), b->v.begin(), b->v.end());
if (a->over || b->over) {
a->over = true;
update(a->v, w);
}
return 1;
}
void rm(dsu *a, int w)
{
a = a->find();
if (!a->over) {
a->over = true;
update(a->v, w);
}
}
void dfs(int v)
{
static int dt = 0;
in[v] = dt++;
for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i].first != f[0][v]) {
f[0][g[v][i].first] = v;
up[0][g[v][i].first] = g[v][i].second;
dfs(g[v][i].first);
}
out[v] = dt;
}
bool parent(int u, int v)
{
return in[u] <= in[v] && out[u] >= out[v];
}
void init(int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> w)
{
memset(fi, 0x3f, n << 2);
for (int i = 0; i < n; ++i) d[i].v.push_back(i);
for (int i = 0; i < m; ++i) e[i] = std::make_pair(w[i], std::make_pair(u[i], v[i]));
std::sort(e, e + m);
for (int i = 0; i < m; ++i) {
bool way = false;
if (unite(d + e[i].second.first, d + e[i].second.second, e[i].first)) {
g[e[i].second.first].push_back(std::make_pair(e[i].second.second, e[i].first));
g[e[i].second.second].push_back(std::make_pair(e[i].second.first, e[i].first));
}
else way = true;
++deg[e[i].second.first];
++deg[e[i].second.second];
if (way || deg[e[i].second.first] == 3 || deg[e[i].second.second] == 3) rm(d + e[i].second.first, e[i].first);
}
dfs(0);
for (int j = 1; j < LG; ++j) for (int i = 0; i < n; ++i) {
f[j][i] = f[j - 1][f[j - 1][i]];
up[j][i] = std::max(up[j - 1][i], up[j - 1][f[j - 1][i]]);
}
}
int getMinimumFuelCapacity(int u, int v)
{
int edge = std::min(fi[u], fi[v]);
for (int t = 0; t < 2; ++t) {
if (!parent(v, u)) {
for (int i = LG - 1; i >= 0; --i) if (!parent(f[i][v], u)) {
edge = std::max(edge, up[i][v]);
v = f[i][v];
}
edge = std::max(edge, up[0][v]);
}
std::swap(u, v);
}
if (edge == INF) return -1;
return edge;
}
