#include<bits/stdc++.h>
#include "swap.h"
using namespace std;
#define ll long long
const int maxn=1e5+5;
ll n,m,f=0;
vector<pair<ll,ll>>v[maxn];
vector<ll>par,dep,lo;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N,m=M;
for(int i=0;i<m;i++){
v[U[i]].push_back({V[i],W[i]});
v[V[i]].push_back({U[i],W[i]});
}
}
void dfs(ll x,ll last,vector<vector<ll>>&adj){
par[x]=last,dep[x]=lo[x]=dep[last]+1;
for(auto i:adj[x]){
if(i==last) continue;
if(dep[i]==0){
dfs(i,x,adj);
lo[x]=min(lo[x],lo[i]);
}
else lo[x]=min(lo[x],dep[i]);
}
if(lo[x]<dep[x]) f=1;
}
bool solve(ll sz,ll X,ll Y){
par.clear();
lo.clear();
dep.clear();
dep.resize(n+5);
par.resize(n+5);
lo.resize(n+5);
f=0;
vector<vector<ll>>adj;
for(int i=0;i<n;i++){
adj.push_back({});
for(auto j:v[i]) if(j.second<=sz) adj.back().push_back(j.first);
}
dfs(X,-1,adj);
if(dep[Y]){
if(f==1) return 1;
Y=par[Y];
while(Y!=X){
if(adj[Y].size()>2) return 1;
Y=par[Y];
}
}
return 0;
}
int getMinimumFuelCapacity(int X, int Y) {
ll l=0,r=1e9+1;
while(l<r){
ll mid=(l+r)/2;
if(solve(mid,X,Y)) r=mid;
else l=mid+1;
}
return ((r==1e9+1)?-1:r);
}
