#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e9;
const int L = 2e5+1;
struct DSU {
int n;
vi dad,change,sz;
DSU(){};
DSU(int nn) {
n = nn;
dad.resize(n),change.assign(n,0),sz.assign(n,1);
iota(dad.begin(),dad.end(),0ll);
}
int find(int x,int t) {
if (!change[x] || change[x] > t) return x;
return find(dad[x],t);
}
void unite(int x,int y,int t) {
int a = find(x,t);
int b = find(y,t);
if (a == b) return;
if (sz[a] < sz[b]) swap(a,b);
dad[b] = a;
sz[a]+=sz[b];
change[b] = t;
}
};
vi vv;
int idx(int xx) {
return upper_bound(all(vv),xx)-vv.begin();
}
struct Node{
int v;
Node *l,*r;
Node() {
l = r = NULL;
v = 0;
}
Node(int x) {
v = x;
l = r = NULL;
}
Node(Node* cp) {
l = cp->l,r = cp->r,v = cp->v;
}
Node(Node* L,Node* R,int V = 0) {
l = L;
r = R;
v = V;
}
};
Node* build(int l,int r) {
if (l == r) return new Node;
int m = (l+r) >> 1;
return new Node(build(l,m),build(m+1,r));
}
Node* update(Node* node,int l,int r,int L,int R,int v) {
if (l >= L && r <= R) return new Node(node->l,node->r,node->v+v);
int m = (l+r) >> 1;
if (m >= L && m+1 <= R) return new Node(update(node->l,l,m,L,R,v),update(node->r,m+1,r,L,R,v),node->v);
if (m >= L) return new Node(update(node->l,l,m,L,R,v),node->r,node->v);
return new Node(node->l,update(node->r,m+1,r,L,R,v),node->v);
}
int query(Node* node,int l,int r,int p) {
if (l == r) return node->v;
int m = (l+r) >> 1;
if (p<=m) return node->v+query(node->l,l,m,p);
return node->v+query(node->r,m+1,r,p);
}
map<int,int> realy;
Node* roots[L];
vi change(L,inf),tin(L),tout(L),par(L),egdes[L];
int timer = 1;
DSU dsu;
int up[L][20];
void dfs(int node,int p) {
par[node] = up[node][0] = p;
tin[node] = timer++;
for (auto it : egdes[node]) if (it != p) dfs(it,node);
tout[node] = timer-1;
}
bool anc(int x,int y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int a,int b) {
if (anc(a,b)) return a;
if (anc(b,a)) return b;
for (int i=19;i>=0;i--) {
if (!anc(up[a][i],b)) a = up[a][i];
}
return up[a][0];
}
int nn;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
nn = N;
for (int i=0;i<M;i++) vv.push_back(W[i]);
sort(all(vv));
vv.erase(unique(all(vv)),vv.end());
int cc = 1;
for (auto it : vv) realy[cc++] = it;
for (int i=0;i<M;i++) {
egdes[U[i]].push_back(V[i]);
egdes[V[i]].push_back(U[i]);
}
dfs(0,0);
for (int i=1;i<20;i++) {
for (int j=0;j<N;j++) up[j][i] = up[up[j][i-1]][i-1];
}
if (M == N-1) {
//tree case
dsu = DSU(N);
vector<pair<int,pii>> edges;
for (int i=0;i<M;i++) edges.push_back({idx(W[i]),{U[i],V[i]}});
sort(all(edges));
for (auto it : edges) dsu.unite(it.ss.ff,it.ss.ss,it.ff);
vi edg(N,0);
int sz = vv.size();
roots[0] = new Node;
roots[0] = build(1,N);
int ptr = 0;
for (int i=1;i<=sz;i++) {
roots[i] = roots[i-1];
while (ptr < edges.size() && edges[ptr].ff == i) {
edg[edges[ptr].ss.ff]++;
edg[edges[ptr].ss.ss]++;
if (edg[edges[ptr].ss.ff] == 3) {
change[edges[ptr].ss.ff] = i;
roots[i] = update(roots[i],1,N,tin[edges[ptr].ss.ff],tout[edges[ptr].ss.ff],1);
}
if (edg[edges[ptr].ss.ss] == 3) {
change[edges[ptr].ss.ss] = i;
roots[i] = update(roots[i],1,N,tin[edges[ptr].ss.ss],tout[edges[ptr].ss.ss],1);
}
ptr++;
}
}
return;
}
assert(0);
}
int getMinimumFuelCapacity(int X, int Y) {
int sz = vv.size();
int l = 1;
int r = sz;
while (l<=r) {
int m = (l+r) >> 1;
if (dsu.find(X,m) != dsu.find(Y,m)) {
l = m+1;
continue;
}
if (!anc(X,Y) && !anc(Y,X)) {
int a = query(roots[m],1,nn,tin[par[X]]);
int b = query(roots[m],1,nn,tin[par[Y]]);
int lc = lca(par[X],par[Y]);
int c = query(roots[m],1,nn,tin[lc]);
if (a+b-2*c+(change[lc]<=m)) r = m-1;
else l = m+1;
continue;
}
if (anc(Y,X)) swap(X,Y);
if (X == par[Y]) {
l = m+1;
continue;
}
int bot = Y;
for (int i=19;i>=0;i--) {
if (!anc(up[bot][i],X)) bot = up[bot][i];
}
int a = query(roots[m],1,nn,tin[par[Y]]);
int b = query(roots[m],1,nn,tin[bot]);
if (a-b+(change[bot]<=m)) r = m-1;
else l = m+1;
}
if (l <= sz) return realy[l];
return -1;
}
