#include "swap.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, inf = 1e9;
int t,n,m,par[N],sz[N],is_chain[N],bec[N],in_deg[N],mx[N];
set < pii > s[N];
vector <int> comp[N];
struct edge {
int x, y, c;
} a[N];
bool cmp(edge a, edge b) {
return a.c < b.c;
}
void my_init() {
for (int i = 1; i <= n; i++) {
par[i] = i; sz[i] = 1; comp[i].pb(i); is_chain[i] = 1;
s[i].insert({0, i});
bec[i] = inf;
is_chain[i] = 1;
}
}
int get_col(int a) {
return par[a];
}
void go(int a, int c){
for (int x : comp[a]) {
bec[x] = c;
}
is_chain[a] = false;
}
void col(int a, int b, int c) {
a = get_col(a);
b = get_col(b);
if (a == b) {
if (is_chain[a]) {
go(a,c);
is_chain[a] = false;
}
return ;
}
if (sz[a] < sz[b]) swap(a,b);
sz[a] += sz[b]; sz[b] = 0;
mx[a] = max(mx[a], mx[b]);
if (is_chain[a] && is_chain[b]) {
if (mx[a] >= 3) {
go(a,c); go(b,c);
}
} else
if (is_chain[a] && !is_chain[b]) go(a,c), is_chain[a] = 0;
else
if (is_chain[b] && !is_chain[a]) go(b,c), is_chain[a] = 0;
for (int vert : comp[b]) comp[a].pb(vert), par[vert] = a, s[vert].insert({c, a});//, cout<<vert<<" --- > "<<a<<" "<<c<<"dros\n";
comp[b].clear();
}
int check(int mid, int a, int b) {
int compa = (*(--s[a].upper_bound({mid,1e9}))).s;
int compb = (*(--s[b].upper_bound({mid, 1e9}))).s;
if (compa == compb && bec[a] <= mid && bec[b] <= mid) return 1;
else return 0;
}
int solve(int x, int y) {
int le = 1, ri = m, ans = 0;
while (le <= ri) {
int mid = (le + ri) / 2;
if(check(mid, x,y)) {
ans = mid;
ri = mid - 1;
} else le = mid + 1;
}
if (ans == 0) return -1;
return a[ans].c;
}
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 = 1; i <= m; i++) {
// cin>>a[i].x>>a[i].y>>a[i].c;
a[i].x = U[i - 1] + 1; a[i].y = V[i - 1] + 1; a[i].c = W[i - 1];
}
sort(a + 1, a + m + 1, cmp);
my_init();
for (int i = 1; i <= m; i++) {
in_deg[a[i].x]++; in_deg[a[i].y]++;
mx[get_col(a[i].x)] = max(mx[get_col(a[i].x)], in_deg[a[i].x]);
mx[get_col(a[i].y)] = max(mx[get_col(a[i].y)], in_deg[a[i].y]);
col(a[i].x, a[i].y, i);
}
}
int getMinimumFuelCapacity(int X, int Y) {
int a = X + 1; int b = Y + 1;
return solve(a,b);
}
