#include "swap.h"
#include <vector>
#include <algorithm>
#include <functional>
#define all(v) v.begin(),v.end()
using namespace std;
struct edge{
int u,v,cost;
};
struct node{
int cost;
bool flag;
};
const int MAX=18;
vector<node> nodes;
vector<vector<int>> child;
vector<int> depth;
vector<vector<int>> par(MAX+1);
vector<int> ans;
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
vector<edge> edges(M);
vector<int> group(N+M);
vector<int> deg(N);
nodes.resize(N+M);
child.resize(N+M);
depth.resize(N+M);
for (int i=0; i<=MAX; i++)
par[i].resize(N+M);
ans.resize(N+M);
for (int i=0; i<M; i++)
edges[i]={U[i],V[i],W[i]};
sort(all(edges),[&](edge a,edge b)->bool{
return a.cost<b.cost;
});
for (int i=0; i<N+M; i++){
group[i]=i;
nodes[i]={0,false};
par[0][i]=i;
}
function<int(int)> getGroup=[&](int v)->int{
if (group[v]==v)
return v;
return group[v]=getGroup(group[v]);
};
for (int i=0; i<M; i++){
edge e=edges[i];
nodes[i+N].cost=e.cost;
deg[e.u]++;
deg[e.v]++;
int u=getGroup(e.u),v=getGroup(e.v);
if (deg[e.u]>2||deg[e.v]>2||nodes[u].flag||nodes[v].flag)
nodes[i+N].flag=true;
if (u==v){
group[u]=i+N;
child[i+N].push_back(u);
par[0][u]=i+N;
nodes[i+N].flag=true;
continue;
}
group[u]=group[v]=i+N;
child[i+N].push_back(u);
child[i+N].push_back(v);
par[0][u]=par[0][v]=i+N;
}
for (int t=1; t<=MAX; t++){
for (int i=0; i<N+M; i++)
par[t][i]=par[t-1][par[t-1][i]];
}
function<void(int)> dfs=[&](int v){
for (int i:child[v]){
depth[i]=depth[v]+1;
ans[i]=(nodes[i].flag?nodes[i].cost:ans[v]);
dfs(i);
}
};
for (int i=0; i<N+M; i++){
if (par[0][i]!=i)
continue;
ans[i]=(nodes[i].flag?nodes[i].cost:-1);
dfs(i);
}
}
int getLCA(int u,int v){
if (depth[u]>depth[v])
swap(u,v);
for (int i=0,t=depth[v]-depth[u]; t; i++,t>>=1){
if (t&1)
v=par[i][v];
}
if (u==v)
return u;
for (int t=MAX; t>=0; t--){
if (par[t][u]!=par[t][v]){
u=par[t][u];
v=par[t][v];
}
}
return par[0][u];
}
int getMinimumFuelCapacity(int X, int Y){
return ans[getLCA(X,Y)];
}
