#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 1e5;
std::set<int> e[N];
std::vector<int> U, V, W;
int n, m;
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
::U = U;
::V = V;
::W = W;
::n = n;
::m = m;
}
std::vector<int> p;
std::vector<bool> vis;
void dfs(int u, int P) {
p[u] = P;
vis[u] = true;
for (auto v : e[u]) {
if (!vis[v]) {
dfs(v, u);
}
}
}
bool check(int X, int Y, int mid) {
for (int i = 0; i < n; i++) e[i].clear();
for (int i = 0; i < m; i++) {
if (W[i] <= mid) {
e[U[i]].emplace(V[i]);
e[V[i]].emplace(U[i]);
}
}
p.assign(n, -1);
vis.assign(n, false);
dfs(X, -1);
if (p[Y] == -1)
return false;
int y = Y;
std::vector<int> got;
y = p[y];
while (y != -1 && p[y] != -1) {
got.push_back(y);
y = p[y];
}
for (auto x : got) {
if (e[x].size() > 2) {
return true;
}
}
if (e[X].size() > 2 || e[Y].size() > 2) {
return true;
}
y = Y;
for (auto x : got) {
e[x].erase(y);
e[y].erase(x);
y = x;
}
e[X].erase(y);
e[y].erase(X);
p.assign(n, -1);
vis.assign(n, false);
dfs(X, -1);
if (p[Y] == -1)
return false;
return true;
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0, r = 1e9 + 2;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(X, Y, mid)) {
r = mid;
} else {
l = mid;
}
}
if (r == 1e9 + 2) r = -1;
return r;
}
