#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
const int MAXN = 3e5+5;
vii adj(MAXN);
int cnt = 0;
vector<int>p(MAXN),deg(MAXN),ans(MAXN,2e9);
vector<bool>can(MAXN);
vii mn(20,vector<int>(MAXN,2e9)),par(20,vector<int>(MAXN,0));
int find(int x){
if(p[x] == x)return x;
else return p[x] = find(p[x]);
}
bool unite(int a,int b){
a = find(a);
b = find(b);
if(a==b)return 0;
p[a] = p[b] = cnt;
can[cnt] = can[a] | can[b];
adj[cnt].pb(a);
adj[cnt].pb(b);
cnt++;
return 1;
}
ll tin[MAXN],tout[MAXN],depth[MAXN];
int timer = 0;
void euler(int v,int u){
tin[v] = timer++;
for(int x:adj[v]){
if(x == u)continue;
euler(x,v);
}
tout[v] = timer;
}
void dfs(int v,int u){
tin[v] = timer++;
if(can[v])mn[0][v] = ans[v];
for(int x:adj[v]){
if(x == u)continue;
par[0][x] = v;
if(can[x]) mn[0][x] = ans[x];
if(can[v]) mn[0][x] = min(mn[0][x],ans[v]);
depth[x] = depth[v]+1;
for(int i=1;i<=19;i++){
par[i][x] = par[i-1][par[i-1][x]];
mn[i][x] = min(mn[i-1][x],mn[i-1][par[i-1][x]]);
}
dfs(x,v);
}
tout[v] = timer;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
if(depth[v] > depth[u])swap(u,v);
int dist = depth[u]-depth[v];
for(int i=0;dist;i++,dist>>=1){
if(dist&1)u = par[i][u];
}
if(u == v)return u;
for(int i=19;i>=0;i--){
if(par[i][v] != par[i][u]){
u = par[i][u];
v = par[i][v];
}
}
return par[0][v];
}
void init(int n, int m,vector<int> u,vector<int> v,vector<int> w) {
vector<pair<int,pii>>e;
cnt=n+1;
for(int i=1;i<=n+m;i++)p[i] = i;
for(int i=0;i<m;i++)e.pb({w[i],{u[i]+1,v[i]+1}});
sort(all(e));
for(auto z : e){
int ww = z.fi;
pii v = z.se;
ans[cnt] = ww;
if(!unite(v.fi,v.se)){
adj[cnt].pb(find(v.fi));
p[find(v.fi)] = cnt;
can[cnt] = 1;
cnt++;
}
else{
deg[v.fi]++;
deg[v.se]++;
if(deg[v.fi]>=3 || deg[v.se]>=3)can[find(v.fi)] = 1;
}
}
dfs(cnt-1,-1);
}
int getMinimumFuelCapacity(int x, int y) {
int v = lca(x+1,y+1);
int a = mn[0][v];
//cout<<v<<'\n';
for(int i=19;i>=0;i--){
if(par[i][v]){
a = min(a,mn[i][v]);
v = par[i][v];
}
}
if(a == 2e9)a=-1;
return a;
}
