#include "swap.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define L(i, j, k) for (int i = (j); i <= k; i++)
#define R(i, j, k) for (int i = (j); i >= k; i--)
const int nax = 100050;
int N, M;
vector<pair<int, int>> G[nax], edges;
void init(int _N, int _M, std::vector<int> _U, std::vector<int> _V, std::vector<int> _W) {
N = _N; M = _M;
L(i, 0, M - 1){
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) {
// notice that either we have a node with degree >= 3
// or that we have a cycle
// since the answer is the maximum, why not consider adding the edge one by one?
vector<bool> ban(M, true), vis(N);
function<void(int, int)> dfs = [&](int u, int f) {
vis[u] = true;
for (auto & v : G[u]) {
if (ban[v.second]) continue;
if (v.first == f) continue;
if (vis[v.first]) continue;
dfs(v.first, f);
}
};
function<bool(int, int)> cycle = [&](int u, int f) {
vis[u] = true;
for (auto & v : G[u]) {
if (ban[v.second]) continue;
if (v.first == f) continue;
if (vis[v.first]) return true;
if (cycle(v.first, u)) return true;
}
return false;
};
function<bool()> degree = [&]() {
for (int i = 0; i < N; i++) {
int deg = 0;
if (vis[i] == true) {
for (auto & v : G[i]) {
deg += ban[v.second] == false;
}
}
if (deg >= 3)
return true;
}
return false;
};
for (int i = 0; i < M; i++) {
int w = edges[i].first;
int id = edges[i].second;
ban[id] = false;
vis = vector<bool>(N);
dfs(X, -1);
if (vis[Y] == false) continue;
vis = vector<bool>(N);
if (cycle(X, -1) || degree()) {
return w;
}
}
return -1;
}
