#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 2e5;
const int inf = 2e9;
int id[M],deg[N];
struct nodedata
{
int parent,active;
};
vector <nodedata> nodes;///parent,active
vector <int> e[2*N - 1];
int p2[2*N - 1][20];
int dpth[2*N - 1];
struct dsu
{
int id,parent,active,sz;
};
dsu v[N];
int leader(int node)
{
if(node == v[node].parent)return node;
int l = leader(v[node].parent);
v[node].parent = l;
return v[node].parent;
}
void connect(int a,int b,int w)
{
deg[a]++;
deg[b]++;
int active = 0;
if(deg[a] >= 3 || deg[b] >= 3)active = 1;
a = leader(a);
b = leader(b);
if(a == b)
{
if(nodes[v[a].id].active == inf)nodes[v[a].id].active = w;
v[a].active = min(v[a].active,w);
}
else
{
nodes[v[a].id].parent = nodes.size();
nodes[v[b].id].parent = nodes.size();
if(v[a].active != inf || v[b].active != inf)active = 1;
if(v[a].sz < v[b].sz)swap(a,b);
v[b].parent = a;
v[a].sz+=v[b].sz;
v[a].id = nodes.size();
nodes.push_back({-1,active?w:inf});
v[a].active = active?w:inf;
}
}
void dfs(int node,int p = -1,int d = 0)
{
dpth[node] = d;
p2[node][0] = p;
for(auto i:e[node])
{
if(i == p)continue;
dfs(i,node,d + 1);
}
}
void init(int n, int m,vector<int> u,vector<int> u2,vector<int> w)
{
int i,j;
for(i = 0; i < m; i++)id[i] = i;
for(i = 0; i < n; i++)
{
nodes.push_back({-1,inf});
v[i] = {i,i,inf,1};
}
sort(id,id + m,[&](int a,int b)
{
return w[a] < w[b];
});
for(i = 0; i < m; i++)
{
///connect u[id[i]] with v[id[i]]
connect(u[id[i]],u2[id[i]],w[id[i]]);
//cout<<u[id[i]]<<' '<<u2[id[i]]<<'\n';
}
int cnt = 0;
for(auto i:nodes)
{
if(i.parent != -1)
{
e[i.parent].push_back(cnt);
}
cnt++;
}
dfs(nodes.size() - 1,nodes.size() - 1);
for(j = 1; j < 20; j++)
{
for(i = 0; i < 2*n - 1; i++)
{
p2[i][j] = p2[p2[i][j - 1]][j - 1];
}
}
/*for(i = 0;i < 2*n - 1;i++){
for(j = 0;j < 20;j++)cout<<p2[i][j]<<' ';
cout<<'\n';
}
for(i = 0;i < 2*n - 1;i++){
cout<<p2[i][0]<<' '<<dpth[i]<<' '<<nodes[i].active<<' '<<i<<'\n';
}*/
}
int getMinimumFuelCapacity(int x, int y)
{
if(nodes[nodes.size() - 1].active == inf)return -1;
if(dpth[x] < dpth[y])swap(x,y);
for(int i = 19; i >= 0; i--)
{
if(dpth[x] - (1<<i) >= dpth[y])
{
x = p2[x][i];
}
}
for(int i = 19; i >= 0; i--)
{
if(p2[x][i] != p2[y][i])
{
x = p2[x][i];
y = p2[y][i];
}
}
if(x != y)x = p2[x][0];
for(int i = 19; i >= 0; i--)
{
if(nodes[p2[x][i]].active == inf)
{
x = p2[x][i];
}
}
if(nodes[x].active == inf)
{
x = p2[x][0];
}
/*while(dpth[x] > dpth[y])x = p2[x][0];
while(x != y)x = p2[x][0],y = p2[y][0];
while(nodes[x].active == inf)x = p2[x][0];*/
return nodes[x].active;
}
/**
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
**/
