//Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
struct Comp
{
int endPoint[2], parent, size, val;
} comp[MAX_N];
int wParent[MAX_N], depth[MAX_N];
vector<int> adj[MAX_N];
int findParent(int node)
{
while (comp[node].parent != -1)
{
node = comp[node].parent;
}
return node;
}
void join(int u, int v, int w)
{
int x = findParent(u), y = findParent(v);
if (x == y)
{
if (comp[x].val < 0)
{
comp[x].val = w;
}
return;
}
if (comp[x].size < comp[y].size)
{
swap(x, y);
swap(u, v);
}
comp[x].size += comp[y].size;
comp[y].parent = x;
wParent[y] = w;
adj[x].push_back(y);
if (comp[x].val < 0 && comp[y].val < 0 && (u == comp[x].endPoint[0] || u == comp[x].endPoint[1]) && (v == comp[y].endPoint[0] || v == comp[y].endPoint[1]))
{
if (u == comp[x].endPoint[0])
{
comp[x].endPoint[0] = comp[x].endPoint[1];
}
comp[x].endPoint[1] = (v == comp[y].endPoint[0] ? comp[y].endPoint[1] : comp[y].endPoint[0]);
}
else if (comp[x].val < 0)
{
comp[x].val = w;
}
}
void dfs(int node)
{
for (auto &u : adj[node])
{
depth[u] = depth[node] + 1;
dfs(u);
}
}
void init(int numNode, int numEdge, vector<int> u, vector<int> v, vector<int> w)
{
vector<int> index(numEdge);
iota(index.begin(), index.end(), 0);
sort(index.begin(), index.end(), [&](int x, int y) { return w[x] < w[y]; });
for (int i = 0; i < numNode; i++)
{
comp[i].endPoint[0] = comp[i].endPoint[1] = i;
comp[i].parent = comp[i].val = -1;
comp[i].size = 1;
}
for (auto &id : index)
{
join(u[id], v[id], w[id]);
}
for (int node = 0; node < numNode; node++)
{
if (comp[node].parent < 0)
{
dfs(node);
}
}
}
int getMinimumFuelCapacity(int u, int v)
{
if (findParent(u) != findParent(v))
{
return -1;
}
int resuft = -1;
while (u != v)
{
if (depth[u] < depth[v])
{
swap(u, v);
}
resuft = max(resuft, wParent[u]);
u = comp[u].parent;
}
while (u >= 0 && comp[u].val < 0)
{
resuft = max(resuft, wParent[u]);
u = comp[u].parent;
}
return (u < 0 ? -1 : max(resuft, comp[u].val));
}
