#include "swap.h"
#include <bits/stdc++.h>
#define see(x) cout<<#x<<"="<<x<<"\n";
using namespace std;
const int N = 1e5+5;
int n, m, used[N], par[N], flag, cycleS, cycleF;
vector <pair <int, int>> g[N];
vector <int> val;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N;
m = M;
for (int i = 0; i < M; i ++) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
val.push_back(W[i]);
}
sort(val.begin(), val.end());
}
void dfs(int v, int p, int k, int x, int y) {
used[v] = 1;
par[v] = p;
if (v != x and v != y and g[v].size() > 2) flag = 1;
for (auto i: g[v]) {
if (i.second > k or i.first == p) continue;
if (used[i.first] and cycleS == -1) {
cycleS = v;
cycleF = i.first;
}
if (!used[i.first]) dfs(i.first, v, k, x, y);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int l = 0, r = m - 1, best = -1;
while (l <= r) {
int mid = (l + r) / 2;
flag = 0;
cycleS = cycleF = -1;
memset(used, 0, sizeof(used));
par[X] = -1;
dfs(X, 0, val[mid], X, Y);
if (cycleS != -1) {
int f1 = 0, f2 = 0;
for (int i = cycleS; i != par[cycleF]; i = par[i]) {
if (i == X) f1 = 1;
if (i == Y) f2 = 1;
}
if (f1 and f2) flag = 1;
}
if (used[Y] and flag) {
best = val[mid];
r = mid - 1;
}
else {
l = mid + 1;
}
}
return best;
}
