#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "swap.h"
const int MAX = 1e5 + 5;
int N, M;
vector<ii> adj[MAX]; // {vertex, dist}
void init(int N_g, int M_g, vi U_g, vi V_g, vi W_g) {
N = N_g;
M = M_g;
for (int i = 0; i < M; i++) {
adj[U_g[i]].pb({V_g[i], W_g[i]});
adj[V_g[i]].pb({U_g[i], W_g[i]});
}
}
bool check(int cut, int X, int Y) {
vi adjc[N];
for (int i = 0; i < N; i++) {
for (ii p : adj[i]) {
if (p.se <= cut)
adjc[i].pb(p.fi);
}
}
vector<bool> vis(N, false);
queue<int> q;
q.push(X);
vis[X] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : adjc[x]) {
if (!vis[y]) {
q.push(y);
vis[y] = true;
}
}
}
if (!vis[Y])
return false;
int cnte = 0; // number of edges
int sz = 0; // number of vertices
for (int i = 0; i < N; i++) {
cnte += adjc[i].size();
if (adjc[i].size() >= 1)
sz++;
}
cnte /= 2;
// cout<<"sz, cnte: "<<sz<<" "<<cnte<<endl;
if (cnte > sz - 1) // has a cycle
return true;
for (int i = 0; i < N; i++) {
if (adjc[i].size() >= 3)
return true;
}
return false;
}
int getMinimumFuelCapacity(int X, int Y) {
// cout<<check(3, X, Y)<<endl;
int low = 0;
int high = 1e9 + 5;
int ans = -1; // minimum so can pass
while (low <= high) { // false, false, false, true, true, true
int mid = (low + high) / 2;
if (check(mid, X, Y)) {
ans = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
return ans;
}
