#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
int n,k,v1=1,v2=1;
vii p,X,Y,Z,arr;
vector<vector<pi>> a;
vi val,low,num;
vector<set<int>> st;
void dfs(int x){
num[x]=v1++;
for(auto u:a[x])if(p[x][0]!=u.F){
p[u.F][0]=x;
X[u.F][0]=u.S;
dfs(u.F);
}
if(x!=0)Y[x][0]=min(Y[x][0],Y[p[x][0]][0]);
low[x]=v2++;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n=N;
k=log2(n)+1;
low.resize(n,0);
num.resize(n,0);
p.resize(n,vi(k,-1));
X.resize(n,vi(k,0));
Y.resize(n,vi(k,inf));
Z.resize(n,vi(k,inf));
a.resize(n);val.resize(n,inf);st.resize(n);
vector<vector<pi>> b(n);arr.resize(n);
REP(i,0,M){
b[U[i]].PB({W[i],V[i]});
b[V[i]].PB({W[i],U[i]});
}
priority_queue<ti,vector<ti>,greater<ti>> pq;
vi dn(n,0);
dn[0]=1;
for(auto u:b[0])pq.push({u.F,u.S,0});
while(!pq.empty()){
int x=get<0>(pq.top());
int y=get<1>(pq.top());
int z=get<2>(pq.top());
pq.pop();
if(dn[y])continue;
a[y].PB({z,x});
a[z].PB({y,x});
arr[y].PB(x);
arr[z].PB(x);
st[y].insert(z);
st[z].insert(y);
dn[y]=1;
for(auto u:b[y])if(dn[u.S]==0)pq.push({u.F,u.S,y});
}
REP(i,0,M)if(st[U[i]].count(V[i])==0){
Y[U[i]][0]=min(Y[U[i]][0],W[i]);
Y[V[i]][0]=min(Y[V[i]][0],W[i]);
}
dfs(0);
REP(i,0,n){
int mn1=inf,mn2=inf;
for(auto u:a[i])if(p[i][0]!=u.F){
if(mn1>u.S){
mn2=mn1;
mn1=u.S;
}
else mn2=min(mn2,u.S);
}
if(a[i].size()>2)val[i]=mn2;
for(auto u:a[i])if(p[i][0]!=u.F){
Z[u.F][0]=mn1;
if(u.S==mn1)Z[u.F][0]=mn2;
}
}
REP(j,1,k)REP(i,0,n)if(p[i][j-1]!=-1){
p[i][j]=p[p[i][j-1]][j-1];
X[i][j]=max(X[i][j],X[p[i][j-1]][j-1]);
Y[i][j]=min(Y[i][j],Y[p[i][j-1]][j-1]);
Z[i][j]=min(Z[i][j],Z[p[i][j-1]][j-1]);
}
REP(i,0,n)sort(arr.begin(),arr.end());
}
bool ances(int x,int y){
if(y==-1)return 1;
if(x==-1)return 0;
return (num[y]<=num[x]&&low[y]>=low[x]);
}
int getMinimumFuelCapacity(int x, int y) {
int ans=0,ans2=inf;
if(ances(x,y))ans2=val[x];
else if(ances(y,x))ans2=val[y];
else ans2=min(val[x],val[y]);
for(int i=k-1;i>=0;i--)if(!ances(y,p[x][i])){
ans=max(ans,X[x][i]);
ans2=min(ans2,Y[x][i]);
ans2=min(ans2,Z[x][i]);
x=p[x][i];
}
for(int i=k-1;i>=0;i--)if(!ances(x,p[y][i])){
ans=max(ans,X[y][i]);
ans2=min(ans2,Y[y][i]);
ans2=min(ans2,Z[y][i]);
y=p[y][i];
}
if(ances(y,x))swap(x,y);
ans=max(ans,X[x][0]);
ans2=min(ans2,Y[x][0]);
if(!ances(x,y)){
ans=max(ans,X[y][0]);
int tmp=p[x][0];
if(arr[tmp].size()>2){
REP(i,0,3)if(arr[tmp][i]!=X[x][0]&&arr[tmp][i]!=X[y][0])ans2=min(ans2,arr[tmp][i]);
}
}
if(max(ans,ans2)==inf)return -1;
return max(ans,ans2);
}
