#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, u, w;
edge(int _v, int _u, int _w)
{
v = _v;
u = _u;
w = _w;
}
};
const int maxn = 4e5 + 10;
const int inf = 1e9 + 10;
int n, m, lead[maxn], rnk[maxn], is_fixed[maxn];
int find_leader(int v)
{
if (v == lead[v])
return v;
return (lead[v] = find_leader(lead[v]));
}
vector < int > g[maxn];
int vertex_cnt, cost[maxn], deg[maxn];
void unite(int v, int u, int w)
{
deg[v] ++;
deg[u] ++;
bool deg_v = (deg[v] > 2), deg_u = (deg[u] > 2);
v = find_leader(v);
u = find_leader(u);
int cur = ++ vertex_cnt;
lead[cur] = cur;
cost[cur] = w;
if (v == u)
{
lead[v] = cur;
is_fixed[cur] = 1;
g[cur].push_back(v);
//cout << cur << " " << v << endl;
return;
}
is_fixed[cur] = max(is_fixed[v], is_fixed[u]);
if (deg_v || deg_u)
is_fixed[cur] = 1;
lead[v] = lead[u] = cur;
g[cur].push_back(v);
g[cur].push_back(u);
//cout << cur << " " << v << endl;
//cout << cur << " " << u << endl;
}
bool cmp(edge e1, edge e2)
{
return e1.w < e2.w;
}
vector < edge > edges;
const int maxlog = 22;
int par[maxn], jump[maxn], timer, lvl[maxn];
int tin[maxn], fs[2 * maxn], lg[2 * maxn], dp[maxlog][2 * maxn];
void dfs(int v)
{
///cout << v << " : " << is_fixed[v] << endl;
if (is_fixed[v])
jump[v] = v;
else
jump[v] = jump[par[v]];
fs[++ timer] = v;
tin[v] = timer;
for (int u : g[v])
{
lvl[u] = lvl[v] + 1;
par[u] = v;
dfs(u);
fs[++ timer] = v;
}
}
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = fs[i];
}
for (int j = 1; j < lg[timer]; j ++)
for (int i = 1; i <= (timer - (1 << j) + 1); i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (lvl[dp[j - 1][i]] < lvl[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
int query_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1, ans = dp[len][r - (1 << len) + 1];
if (lvl[dp[len][l]] < lvl[ans])
ans = dp[len][l];
return ans;
}
void init(int N, int M,
vector<int> U, vector<int> V, vector<int> W)
{
n = N;
m = M;
for (int i = 0; i < m; i ++)
{
edges.push_back(edge(U[i], V[i], W[i]));
}
for (int i = 0; i < n; i ++)
lead[i] = i;
vertex_cnt = n - 1;
sort(edges.begin(), edges.end(), cmp);
for (int i = 0; i < edges.size(); i ++)
{
unite(edges[i].v, edges[i].u, edges[i].w);
}
lvl[vertex_cnt] = 1;
jump[vertex_cnt + 1] = vertex_cnt + 1;
par[vertex_cnt] = vertex_cnt + 1;
dfs(vertex_cnt);
build_sparse_table();
}
int getMinimumFuelCapacity(int X, int Y)
{
int lca = query_lca(X, Y);
lca = jump[lca];
if (lca == vertex_cnt + 1)
return -1;
///cout << "lca " << lca << endl;
return cost[lca];
}
