#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
#define all(x) x.begin() , x.end()
const int N = 1e5;
int n , m;
vector<int> u , v , w;
vector<vector<array<int ,3>>> adj;
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
n = N , m = M , u = U , v = V , w = W;
adj.assign(n , {});
for (int i = 0 ; i < M ; i++){
adj[U[i]].push_back({V[i] , W[i] , i});
adj[V[i]].push_back({U[i] , W[i] , i});
}
int cnt = M;
for (int i = 0 ; i < N ; i++) adj[i].push_back({i , 0 , cnt++});
}
bool check(int x , int y , int md){
bool vis[n][n] = {};
queue<array<int , 2>> qu;
vis[x][y] = 1;
qu.push({x , y});
while(!qu.empty()){
auto &[x , y] = qu.front(); qu.pop();
for (auto &[i , d , id1] : adj[x]){
if (d > md) continue;
for (auto &[j , e , id2] : adj[y]){
if (i == j || d > md || e > md || id1 == id2) continue;
if (!vis[i][j]){
vis[i][j] = 1;
qu.push({i , j});
}
}
}
}
return vis[y][x];
}
int getMinimumFuelCapacity(int X, int Y) {
if (!check(X , Y , 1e9)) {return -1; }
int l = 0 , r = 1.5e9 , md;
while(l<=r){
md = (l+r)/2;
if (check(X , Y , md)) r = md-1;
else l = md+1;
}
return r+1;
}
