P5236 [Template] Static Cactus

This is a template problem for the Static Cactus (Block Forest Data Structure). If you do not know what a cactus is, here is the definition of an undirected cactus graph: > An undirected connected graph in which any edge appears in at most one simple cycle is called a cactus.

You are given a cactus graph with $n$ vertices and $m$ edges, and $q$ queries. Each query gives two vertices $u, v$. Find the shortest path distance between them. The input is guaranteed to have no multiple edges.

The first line contains three positive integers $n, m, q$, with the meanings as described above. The next $m$ lines each contain three positive integers $u, v, w$, indicating an undirected edge between $u$ and $v$ with weight $w$. Then follow $q$ lines, each containing two positive integers $u, v$, asking for the shortest path from $u$ to $v$.

Output $q$ lines, each with one positive integer, the answer for the corresponding query.

**Explanation for Sample 1:** The cactus in Sample 1 looks like this:  There are two queries: the shortest path for $1\rightarrow 9$ and for $5\rightarrow 7$. Obviously, the answers are $5$ and $6$. **Constraints:** $1\le n, q \le 10000$ $1\le m \le 20000$ $1\le w \le 10^5$ The input is guaranteed to have no multiple edges. Note that the time limit is $300\text{ms}$. Translated by ChatGPT 5