#include "swap.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll INF = 1e15;
vector<vector<ll>> adj, up;
vector<ll> s, p, v2, dg, v3, v4, dist;
vector<tuple<ll, ll, ll>> edges;
ll cnt = 0, n;
ll _find(ll x)
{
if (p[x] != x)
p[x] = _find(p[x]);
return p[x];
}
void _union(ll a, ll b, ll w)
{
ll x = a, y = b;
a = _find(a), b = _find(b);
if (a == b)
{
adj[cnt].push_back(v3[a]);
adj[v3[a]].push_back(cnt);
dg[x]++;
dg[y]++;
v2[cnt] = 1;
v4[cnt] = w;
v3[a] = cnt++;
return;
}
adj[cnt].push_back(v3[a]);
adj[v3[a]].push_back(cnt);
adj[cnt].push_back(v3[b]);
adj[v3[b]].push_back(cnt);
dg[x]++;
dg[y]++;
if (dg[x] >= 3 || dg[y] >= 3)
v2[cnt] = 1;
if (v2[v3[a]] || v2[v3[b]])
v2[cnt] = 1;
v4[cnt] = w;
if (s[a] < s[b])
swap(a, b);
v3[a] = cnt;
s[a] += s[b];
p[b] = a;
cnt++;
}
void dfs(ll node, ll parent, ll val)
{
up[node][0] = parent;
if (v2[node])
val = v4[node];
v4[node] = val;
if (dist[parent] - dist[up[parent][1]] == dist[up[parent][1]] - dist[up[up[parent][1]][1]])
up[node][1] = up[up[parent][1]][1];
else
up[node][1] = parent;
for (ll to : adj[node])
{
if (to == parent)
continue;
dist[to] = dist[node] + 1;
dfs(to, node, val);
}
}
ll lca(ll a, ll b)
{
if (dist[a] < dist[b])
swap(a, b);
while (dist[a] > dist[b])
{
if (dist[up[a][1]] >= dist[b])
a = up[a][1];
else
a = up[a][0];
}
if (a == b)
return v4[a];
while (up[a][0] != up[b][0])
{
if (up[a][1] != up[b][1])
{
a = up[a][1];
b = up[b][1];
}
else
{
a = up[a][0];
b = up[b][0];
}
}
return v4[up[a][0]];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
n = N;
cnt = N;
adj.assign(N + M + 10, {});
up.assign(N + M + 10, vector<ll>(2));
p.resize(N + 1);
s.assign(N + 1, 1);
dg.assign(N + 1, 0);
v2.assign(N + M + 10, 0);
v3.resize(N + M + 10);
v4.resize(N + M + 10);
dist.assign(N + M + 10, 0);
iota(p.begin(), p.end(), 0);
iota(v3.begin(), v3.end(), 0);
edges.clear();
for (int i = 0; i < M; i++)
{
edges.emplace_back(W[i], V[i], U[i]);
}
sort(edges.begin(), edges.end());
for (auto &[w, y, x] : edges)
_union(x, y, w);
up[cnt - 1][0] = up[cnt - 1][1] = cnt - 1;
dfs(cnt - 1, cnt - 1, -1);
}
int getMinimumFuelCapacity(int X, int Y)
{
return lca(X, Y);
}
