#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, u, w;
};
const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;
vector < edge > g[maxn];
int n, m;
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 ++)
{
edge e;
e.u = V[i];
e.w = W[i];
g[U[i]].push_back(e);
e.u = U[i];
g[V[i]].push_back(e);
}
}
int used[maxn], deg[maxn], edge_cnt;
void dfs(int v, int lim)
{
used[v] = 1;
for (edge nb : g[v])
{
if (nb.w > lim)
continue;
edge_cnt ++;
deg[v] ++;
if (used[nb.u])
continue;
dfs(nb.u, lim);
}
}
bool check(int x, int y, int fuel)
{
for (int i = 0; i < n; i ++)
{
used[i] = deg[i] = 0;
}
edge_cnt = 0;
dfs(x, fuel);
if (!used[y])
return false;
edge_cnt /= 2;
int used_ver = 0;
bool deg3 = false;
for (int i = 0; i < n; i ++)
{
used_ver += used[i];
if (deg[i] > 2)
deg3 = true;
}
if (edge_cnt >= used_ver || deg3)
return true;
return false;
}
int getMinimumFuelCapacity(int X, int Y)
{
int left = 0, right = inf;
while(left <= right)
{
int mid = (left + right) / 2;
if (check(X, Y, mid))
right = mid - 1;
else
left = mid + 1;
}
if (left > inf)
return - 1;
return left;
}
