#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
const int INF = 1e9 + 10;
struct DSU {
vector<int> p, r;
void init(int n) {
p.assign(n, 0);
r.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
return p[x] = (p[x] == x ? x : find(p[x]));
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (r[u] < r[v]) swap(u, v);
p[v] = u;
r[u] += r[v];
}
};
struct edge {
int u, v, w;
};
int n, m;
vector<pair<int, int>> G[N];
vector<edge> edges;
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W) {
n = N, m = M;
edges.resize(m);
for (int i = 0; i < m; i++) {
edges[i] = {U[i], V[i], W[i]};
G[U[i]].push_back({V[i], W[i]});
G[V[i]].push_back({U[i], W[i]});
}
sort(edges.begin(), edges.end(), [](edge x, edge y) {
return (x.w < y.w);
});
}
vector<int> g[N];
vector<bool> vis;
vector<int> par;
void travel(int s) {
vis[s] = true;
for (int to : g[s]) if (!vis[to]) {
par[to] = s;
travel(to);
}
}
vector<int> find_path(int x, int y) {
vis.assign(n, 0);
par.assign(n, 0);
travel(x);
assert(vis[y]);
vector<int> res;
while (y != x) {
res.push_back(y);
y = par[y];
}
res.push_back(x);
reverse(res.begin(), res.end());
return res;
}
int getMinimumFuelCapacity(int X, int Y) {
for (int i = 0; i < n; i++)
g[i].clear();
int res = -INF, mn = INF;
DSU ds;
ds.init(n);
for (auto [u, v, w] : edges) {
ds.unite(u, v);
g[u].push_back(v);
g[v].push_back(u);
if (ds.find(X) == ds.find(Y)) {
res = w;
break;
}
}
set<pair<int, int>> deleted;
vector<int> vertices = find_path(X, Y);
for (int i = 0; i < (int)vertices.size() - 1; i++) {
deleted.insert({vertices[i], vertices[i + 1]});
deleted.insert({vertices[i + 1], vertices[i]});
}
for (int u : vertices) {
if (u == X || u == Y) continue;;
for (auto [to, w] : G[u])
if (!deleted.count({u, to})) {
mn = min(mn, w);
}
}
ds.init(n);
for (auto [u, v, w] : edges) {
if (deleted.count({u, v})) continue;
ds.unite(u, v);
if (ds.find(X) == ds.find(Y)) {
mn = min(mn, w);
break;
}
}
if (mn == INF) return -1;
return max(mn, res);
}
