#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vvp g;
vll pr, id, mn, gus, sz, dep;
vi w;
vector<pair<pll,ll>> bs;
ll find_gus(ll a){
if(gus[a]==a)return a;
return gus[a] = find_gus(gus[a]);
}
ll unite(ll a, ll b){
a=find_gus(a);
b=find_gus(b);
if(a==b)return 0;
if(sz[a]<sz[b])swap(a,b);
gus[b]=a;
sz[a]+=sz[b];
return 1;
}
void dfs(ll cur, ll d=0){
bs[cur] = {{1e15,1e15},(ll)1e15};
dep[cur] = d;
for(auto [i, e]: g[cur]){
if(i==pr[cur])continue;
pr[i]=cur;
id[i]=e;
if(w[e]<bs[cur].f.f){
bs[cur].s=bs[cur].f.s;
bs[cur].f.s=bs[cur].f.f;
bs[cur].f.f=w[e];
}
else if(w[e]<bs[cur].f.s){
bs[cur].s=bs[cur].f.s;
bs[cur].f.s=w[e];
}
else if(w[e]<bs[cur].s){
bs[cur].s=w[e];
}
dfs(i, d+1);
}
}
ll find_pr(ll a){
if(a==0 || mn[id[a]]==1e15)return a;
return pr[a]=find_pr(pr[a]);
}
vvl up, cir, we;
void init(int n, int m, vi u, vi v, vi W) {
bs=vector<pair<pll,ll>>(n);
w=W;
vll ord(m), sp(m);
iota(all(ord), 0ll);
sort(all(ord), [&](ll i, ll j){return w[i]<w[j];});
dep = pr = id = gus = sz = vll(n,1);
iota(all(gus),0ll);
mn = vll(m, 1e15);
g = vvp(n);
for(ll i: ord){
if(unite(u[i],v[i])){
sp[i]=1;
g[u[i]].pb({v[i],i});
g[v[i]].pb({u[i],i});
}
}
id[0]=pr[0]=-1;
dfs(0);
for(ll i: ord){
if(!sp[i]){
ll a = u[i], b=v[i];
a=find_pr(a);
b=find_pr(b);
while(a!=b){
if(dep[b]>dep[a])swap(a,b);
mn[id[a]]=w[i];
a=find_pr(a);
}
}
}
up=cir=we = vvl(20, vll(n));
for(ll i = 1; i < n; ++i){
cir[0][i] = mn[id[i]];
if(bs[pr[i]].f.f==w[id[i]])cir[0][i] = min(cir[0][i], bs[pr[i]].f.s);
else cir[0][i] = min(cir[0][i], bs[pr[i]].f.f);
we[0][i]=w[id[i]];
up[0][i]=pr[i];
}
for(ll f = 1; f < 20; ++f){
for(ll i = 0; i < n; ++i){
up[f][i] = up[f-1][up[f-1][i]];
cir[f][i] = min(cir[f-1][i], cir[f-1][up[f-1][i]]);
we[f][i] = max(we[f-1][i], we[f-1][up[f-1][i]]);
}
}
}
int getMinimumFuelCapacity(int x, int y) {
ll ci=1e15, ww=0;
if(dep[x]<dep[y])swap(x,y);
ll d = dep[x]-dep[y];
for(ll i = 19; i >= 0; --i){
if(d>(1<<i)){
d-=(1<<i);
ci = min(ci, cir[i][x]);
ww = max(ww, we[i][x]);
x = up[i][x];
}
}
if(pr[x]!=y && d>0){
ci = min(ci, cir[0][x]);
ww = max(ww, we[0][x]);
x = up[0][x];
}
else if(d>0){
ci = min(ci, mn[id[x]]);
ww = max(ww, we[0][x]);
x = up[0][x];
}
if(ci==1e15 && x==y)return -1;
if(x==y)return max(ww,ci);
for(ll i = 19; i >= 0; --i){
if(up[i][x]!=up[i][y]){
ci = min(ci, cir[i][x]);
ww = max(ww, we[i][x]);
x = up[i][x];
ci = min(ci, cir[i][y]);
ww = max(ww, we[i][y]);
y = up[i][y];
}
}
if(w[id[x]]>w[id[y]])swap(x,y);
if(w[id[x]]!=bs[pr[x]].f.f)ci = min(ci, bs[pr[x]].f.f);
else if(w[id[y]]!=bs[pr[x]].f.s)ci = min(ci, bs[pr[x]].f.s);
else ci = min(ci, bs[pr[x]].s);
ci = min(ci, mn[id[x]]);
ww = max(ww, we[0][x]);
x = up[0][x];
ci = min(ci, mn[id[y]]);
ww = max(ww, we[0][y]);
y = up[0][y];
if(ci==1e15 && x==y)return -1;
if(x==y)return max(ww,ci);
}
