#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int nax = 1005;
int N, M;
vector<pair<int, int>> edges; // (W, index)
vector<pair<int, int>> G[nax]; // (V, index of the edge)
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++) {
G[U[i]].push_back(make_pair(V[i], i));
G[V[i]].push_back(make_pair(U[i], i));
edges.push_back(make_pair(W[i], i));
}
sort(edges.begin(), edges.end());
}
int getMinimumFuelCapacity(int X, int Y) {
vector<bool> vis(N);
vector<bool> ban(M, true);
function<void(int, int)> dfs = [&](int u, int f) {
// u = current node, f = node that we came from
// u -> f, f -> u
vis[u] = true;
for (auto v : G[u]) {
if (v.first == f) continue;
if (ban[v.second]) continue;
if (!vis[v.first]) dfs(v.first, u);
}
};
function<bool(int, int)> cycle = [&](int u, int f) {
// u = current node, f = node that we came from
// u -> f, f -> u
vis[u] = true;
for (auto v : G[u]) {
if (v.first == f) continue;
if (ban[v.second]) continue;
if (vis[v.first]) return true;
// v -> f -> u -> v return true
if (cycle(v.first, u)) return true;
}
return false;
};
function<bool()> degree3 = [&]() {
for (int i = 0; i < N; i++) {
if (vis[i] == false) continue;
int deg = 0;
for (auto & v : G[i]) {
if (ban[v.second] == false) {
deg++;
if (deg >= 3) return true;
}
}
}
return false;
};
for (int i = 0; i < M; i++) {
vis = vector<bool>(N);
int w = edges[i].first;
int id = edges[i].second;
ban[id] = false;
dfs(X, -1);
if (vis[Y] == false) continue;
if (degree3()) return w;
vis = vector<bool>(N);
if (cycle(X, -1)) return w;
}
return -1;
}
// #include "grader.cpp"
