#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second
vector<pair<int, ii> > edges;
int n, m;
vi p(100001), sz(100001, 1), s(100001), e(100001), line(100001, -1), sub(100001);
vi d(100001), g[100001];
int get(int a){
if (p[a] == a) return a;
return get(p[a]);
}
void Union(int a, int b, int w){
int c = get(a); int d = get(b);
if (c == d){
if (line[c] == -1) line[c] = w;
return;
}
if (sz[c] < sz[d]){
swap(c, d); swap(a, b);
}
p[d] = c;
sz[c] += sz[d];
sub[d] = w;
if (line[c] == -1 && line[d] == -1){
if (s[c] == a && b == s[d]){
s[c] = e[d]; return;
}
if (s[c] == a && b == e[d]){
s[c] = s[d]; return;
}
if (e[c] == a && b == s[d]){
e[c] = e[d]; return;
}
if (e[c] == a && b == e[d]){
e[c] = s[d]; return;
}
line[c] = w; return;
}
if (line[c] == -1) line[c] = w;
}
void init(int N, int M, vi U, vi V, vi W) {
n = N; m = M;
FOR(i, 0, m){
edges.pb({W[i], {U[i], V[i]}});
}
FOR(i, 0, n){
p[i] = i;
s[i] = i;
e[i] = i;
}
sort(edges.begin(), edges.end());
FOR(i, 0, m){
Union(edges[i].S.F, edges[i].S.S, edges[i].F);
}
int head;
FOR(i, 0, n){
if (p[i] != i){
g[p[i]].pb(i); continue;
}
head = i;
}
vi bfs; bfs.pb(head);
FOR(i, 0, bfs.size()){
int u = bfs[i];
for (int v : g[u]){
d[v] = d[u] + 1;
bfs.pb(v);
}
}
}
int getMinimumFuelCapacity(int x, int y) {
int l = 0, r = 1000000001;
while (r-l > 1){
int u = x; int v = y;
int m = (l+r)/2;
while(sub[u] <= m && u != p[u]){
u = p[u];
}
while(sub[v] <= m && v != p[v]){
v = p[v];
}
if (u == v && line[u] <= m && line[u] != -1){
r = m;
}else{
l = m;
}
}
if (r == 1000000001) return -1;
else return r;
return -1;
}
