Background

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.

Problem Description

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.

Input Format

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 Format

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

9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7

5
6

9 10 3
1 2 1
2 3 1
2 4 4
3 4 2
4 5 1
5 6 1
6 7 2
7 8 2
8 9 4
5 9 2
1 9
5 8
3 4

7
5
2

Hint

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