#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 3e5+15;
const int INF = 1e9+10;
const int LOG = 20;
const int MOD = 1e9+7;
void chmx(int &a,int b){ a = max(a, b); }
void chmn(int &a, int b){ a = min(a, b); }
int n, m;
vector <ipii> edge;
int cnt, anc[MAXN][LOG+5], val[MAXN][LOG+5];
vector <int> adj[MAXN];
int dep[MAXN];
void dfs(int nw, int par){
dep[nw] = dep[par]+1;
for(auto nx : adj[nw])
dfs(nx, nw);
}
struct dsu {
int par[MAXN], le[MAXN], ri[MAXN];
bool tag[MAXN];
void bd(){
tag[0] = 1;
for(int i=1; i<=n+m; i++){
par[i] = le[i] = ri[i] = i;
}
}
int f(int x){
return (par[x]==x ? x : par[x]=f(par[x]));
}
bool con(int x, int y){
return f(x) == f(y);
}
void mer(int x, int y){
x = f(x); y = f(y);
if(x==y) return;
par[y] = x;
}
void gab(int a, int x, int y){
int b = f(x), c = f(y);
tag[a] = (tag[b] | tag[c]);
int p = -1;
if(x==le[b] || y==le[b]) p = ri[b];
if(x==ri[b] || y==ri[b]) p = le[b];
int q = -1;
if(x==le[c] || y==le[c]) q = ri[c];
if(x==ri[c] || y==ri[c]) q = le[c];
le[a] = p; ri[a] = q;
if(p==-1 || q==-1) tag[a] = 1;
mer(a, x); mer(a, y);
}
} DSU;
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++)
edge.pb({W[i], {U[i]+1, V[i]+1}});
for(int j=0; j<LOG; j++)
for(int i=0; i<=n+m; i++)
val[i][j] = INF;
sort(edge.begin(), edge.end());
DSU.bd();
cnt = n;
for(auto [wei, p] : edge){
int x = p.fi, y = p.se;
cnt++;
if(DSU.con(x, y)){
val[DSU.f(x)][0] = wei;
anc[DSU.f(x)][0] = cnt;
adj[cnt].pb(DSU.f(x));
DSU.mer(cnt, x);
DSU.tag[cnt] = 1;
} else {
val[DSU.f(x)][0] = wei;
val[DSU.f(y)][0] = wei;
anc[DSU.f(x)][0] = cnt;
anc[DSU.f(y)][0] = cnt;
adj[cnt].pb(DSU.f(x)); adj[cnt].pb(DSU.f(y));
DSU.gab(cnt, x, y);
}
// cout << x <<' ' << y << " pq\n";
// for(int p=1; p<=7; p++){
// cout << p << ' ' << DSU.f(p) << ' ' << DSU.le[p]<<' '<<DSU.ri[p]<< " p\n";
// }
}
dfs(n+m, 0);
for(int j=1; j<LOG; j++){
for(int i=1; i<=n+m; i++){
anc[i][j] = anc[anc[i][j-1]][j-1];
val[i][j] = max(val[i][j-1], val[anc[i][j-1]][j-1]);
}
}
}
int getMinimumFuelCapacity(int X, int Y) {
X++; Y++;
int mx = 0;
// cout << dep[X]<< ' ' << dep[Y] << " dep\n";
if(dep[X] < dep[Y]) swap(X, Y);
for(int i=LOG-1; i>=0; i--){
if(dep[anc[X][i]] >= dep[Y]){
chmx(mx, val[X][i]);
X = anc[X][i];
}
}
if(X != Y){
for(int i=LOG-1; i>=0; i--){
if(anc[X][i] != anc[Y][i]){
chmx(mx, max(val[X][i], val[Y][i]));
X = anc[X][i]; Y = anc[Y][i];
}
}
// cout << X << ' '<< Y << "awal\n";
chmx(mx, val[X][0]); X = anc[X][0];
// cout<< X << " x\n";
}
if(DSU.tag[X]) return mx;
int mn = INF;
for(int i=LOG-1; i>=0; i--){
if(DSU.tag[anc[X][i]]) chmn(mn, max(mx,val[X][i]) );
else {
chmx(mx, val[X][i]);
X = anc[X][i];
}
}
if(DSU.tag[anc[X][0]]) chmn(mn, max(mx,val[X][0]) );
return (mn>=INF ? -1 : mn);
}
