/*#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/
#include <bits/stdc++.h>
#include "swap.h"
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
//#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
//using namespace __gnu_pbds;
const ll INF = 1e18+7;
const int lg = 20;
//const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
mt19937 rng(1488);
ll randll(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
vpll p;
vll s, cnt;
ll find(ll v, ll t) {
if (p[v].fr == v || p[v].se > t) return v;
return find(p[v].fr, t);
}
void unite(ll a, ll b, ll t, bool q) {
a = find(a, t);
b = find(b, t);
if (a == b) {
cnt[a] = min(cnt[a], t);
return;
}
if (s[a] < s[b]) {
p[a] = {b, t};
s[b] += s[a];
cnt[b] = min(cnt[b], cnt[a]);
if (q) cnt[b] = min(cnt[b], t);
}
else {
p[b] = {a, t};
s[a] += s[b];
cnt[a] = min(cnt[b], cnt[a]);
if (q) cnt[a] = min(cnt[a], t);
}
}
void init(int n, int m, vi u, vi v, vi W) {
vector<pair<ll, pll>> a(m);
for (int i = 0; i < m; i ++) {
a[i] = {W[i], {u[i], v[i]}};
}
sort(a);
vll k(n+7, 0);
p.clear();
s.clear();
cnt.clear();
s.resize(n+7, 1);
cnt.resize(n+7, INF);
p.resize(n+7);
for (int i = 0; i <= n; i ++) {
p[i] = {i, -1};
}
for (auto i : a) {
k[i.se.fr] ++;
k[i.se.se] ++;
unite(i.se.fr, i.se.se, i.fr, (k[i.se.se] >= 3 || k[i.se.fr] >= 3));
}
}
int getMinimumFuelCapacity(int x, int y) {
ll l = -1, r = 1e9+7;
while (r-l > 1) {
ll t = (l+r)/2;
if (find(x, t) == find(y, t) && cnt[find(x, t)] <= t) r = t;
else l = t;
}
if (r == 1e9+7) return -1;
return r;
}
/*int main(){
speed;
srand(time(0));
ll q;
cin >> q;
init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
while (q --) {
ll x, y;
cin >> x >> y;
cout << getMinimumFuelCapacity(x, y) << endl;
}
}*/
