Background

This is a template problem for the Static Cactus (Block Forest Data Structure).
If you are unfamiliar with what a cactus is, here is the definition for an undirected cactus graph:

An undirected connected graph where each 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 asks for the shortest path between two points $u$ and $v$.

The input data guarantees no duplicate edges.

Input Format

The first line contains three positive integers $n, m, q$, as described in the problem statement.
The next $m$ lines each contain three positive integers $u, v, w$, indicating an undirected edge between $u$ and $v$ with weight $w$.
The following $q$ lines each contain two positive integers $u, v$, representing a query for the shortest path from $u$ to $v$.

Output Format

Output $q$ lines, each containing a positive integer corresponding to the result of each query.

Sample Input and Output

Input Sample #1

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

Output Sample #1

5
6

Input Sample #2

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

Output Sample #2

7
5
2

Notes

Sample 1 Explanation:
The cactus in Sample 1 looks like this:

There are two queries, asking for the shortest paths from $1$ to $9$ and from $5$ to $7$.
The answers are clearly $5$ and $6$ respectively.

Data Range:
$1 \le n, q \le 10000$
$1 \le m \le 20000$
$1 \le w \le 10^5$

The input data guarantees no duplicate edges.

Please note that the time limit is $300\text{ms}$.

见题面 Input 部分

见题面 Output 部分