#include "swap.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 1e5+10;
int pp[MAXN];
int id[MAXN];
int cal[MAXN];
int chk[MAXN*3];
int val[MAXN*3];
int ch[MAXN*3][3];
int vid[MAXN*3];
int depth[MAXN*3];
int par[MAXN*3][20];
vector<pii> edge[MAXN*2];
int root(int x){
if(pp[x]==x)return x;
else return pp[x] = root(pp[x]);
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
for(int i=0;i<N;i++){
pp[i] = i;
id[i] = i;
ch[i][0] = -1;
ch[i][1] = -1;
}
vector<int> pos = W;
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
int sz = (int)pos.size();
int idx = -1,idy = - 1;
for(int i=0;i<M;i++){
idx = lower_bound(pos.begin(),pos.end(),W[i])-pos.begin();
edge[idx].push_back(pii(U[i],V[i]));
}
int seq = N-1;
int cur = 0;
int x,y;
int a,b;
for(int i=0;i<sz;i++){
cur = pos[i];
for(int j=0;j<(int)edge[i].size();j++){
x = edge[i][j].f;
y = edge[i][j].s;
cal[x]++;
cal[y]++;
a = root(x);
b = root(y);
idx = id[a];
idy = id[b];
seq++;
if(a^b){
pp[b] = a;
id[a] = seq;
chk[seq] = chk[idx]|chk[idy];
if(cal[x]>=3||cal[y]>=3)chk[seq] = 1;
val[seq] = cur;
par[idx][0] = seq;
par[idy][0] = seq;
ch[seq][0] = idx;
ch[seq][1] = idy;
}
else {
id[a] = seq;
chk[seq] = 1;
val[seq] = cur;
par[idx][0] = seq;
ch[seq][0] = idx;
ch[seq][1] = -1;
}
}
}
par[seq][0] = seq;
vid[seq] = -1;
for(int i=seq;i>=0;i--){
if(chk[i])vid[i] = i;
if(ch[i][0]!=-1){
vid[ch[i][0]] = vid[i];
depth[ch[i][0]] = depth[i]+1;
}
if(ch[i][1]!=-1){
vid[ch[i][1]] = vid[i];
depth[ch[i][1]] = depth[i]+1;
}
}
for(int j=1;j<20;j++){
for(int i=0;i<=seq;i++){
par[i][j] = par[par[i][j-1]][j-1];
}
}
/*
for(int i=0;i<=seq;i++){
cout<<i<<" "<<par[i][0]<<"\n";
cout<<ch[i][0]<<" "<<ch[i][1]<<"\n";
cout<<chk[i]<<" "<<val[i]<<" "<<vid[i]<<" "<<depth[i]<<"\n";
}
for(int i=0;i<=seq;i++){
for(int j=0;j<=10;j++){
cout<<par[i][j]<<" ";
}
cout<<"\n";
}*/
return;
}
int getMinimumFuelCapacity(int X, int Y) {
if(depth[X]>depth[Y])swap(X,Y);
int d = depth[Y]-depth[X];
for(int i=19;~i;i--){
if((1<<i)&d)Y = par[Y][i];
}
for(int i=19;~i;i--){
if(par[X][i]^par[Y][i])X = par[X][i],Y = par[Y][i];
}
int lc = -1;
if(X^Y)lc = par[X][0];
else lc = X;
//cout<<lc<<"\n";
int ver = vid[lc];
if(ver==-1)return -1;
else return val[ver];
}
