Problem Description

For an integer sequence $p_1,\ldots,p_n$, we call $p_i$ a prefix maximum if and only if there does not exist $1\le j<i$ such that $p_j\ge p_i$.

For an integer sequence $p_1,\ldots,p_n$, define its weight as the number of its prefix maxima.

Xiaoxun has a connected graph with $n$ vertices and $m$ undirected edges, where the vertices are numbered from $1$ to $n$. It is guaranteed that the graph is connected, but it is not guaranteed to be a simple graph.

Yinli has $q$ queries. In each query, two vertices $s,t$ are given. You need to find a path $p_1, \dots, p_k$ that starts from vertex $s$ and ends at vertex $t$ ($p_1 = s$, $p_k = t$, and there is an edge connecting $p_i$ and $p_{i + 1}$), such that the weight of the sequence $p_1, \ldots, p_k$ is minimized. You only need to output the minimum weight.

In particular, the path is not required to be a simple path. That is, it may pass through repeated edges or vertices.

Input Format

The first line contains three positive integers $n,m,q$.

The next $m$ lines each contain two positive integers $u,v$, representing an edge connecting vertices $u$ and $v$.

The next $q$ lines each contain two positive integers $s,t$, representing a query.

Output Format

Output $q$ lines, each containing one positive integer, denoting the answer to the corresponding query.

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

2
1
2
2

20 20 20
8 19
19 11
11 18
11 20
20 9
18 13
19 1
11 16
19 5
1 2
2 15
18 6
16 7
8 10
5 4
18 14
11 17
10 12
7 3
1 9
13 14
11 18
13 16
13 16
3 14
20 20
16 18
14 19
8 19
5 20
7 17
14 15
16 18
7 18
6 10
16 17
14 19
3 16
20 20
20 20

2
2
2
2
4
1
2
3
2
3
3
3
2
3
3
2
3
3
1
1

Hint

[Sample Explanation #1]

The sample graph is as follows:

• For the query $2,7$, one path with minimum weight is $(2,1,8,3,6,7)$, and its weight is $2$.
• For the query $4,3$, one path with minimum weight is $(4,3)$, and its weight is $1$.
• For the query $5,4$, one path with minimum weight is $(5,2,6,3,4)$, and its weight is $2$.
• For the query $3,8$, one path with minimum weight is $(3,8)$, and its weight is $2$.

[Constraints]

This problem uses bundled testdata.

• Special Property A: It is guaranteed that $m=n-1$.
• Special Property B: It is guaranteed that for any $i\in[1,n]$, the induced subgraph with $V'=\{1,2,\ldots,i\}$ is connected.

For $100\%$ of the testdata, it is guaranteed that $1\le n,m,q\leq 2\times 10^5$, $1\le u,v,s,t\le n$. The graph is guaranteed to be connected, but it is not guaranteed that there are no multiple edges or self-loops.

Translated by ChatGPT 5