Problem Description

In the Takahashi Kingdom, there are $ N $ cities $1,\ 2,\ ...,\ N$. Direct teleportation devices are installed between any two different cities. Using the teleportation device connecting cities $ x $ and $ y $, one can move from city $ x $ to city $ y $ and from city $ y $ to city $ x $.

However, currently, the teleportation devices connecting cities $ a_i $ and $ b_i $ ($i\ =\ 1,\ 2,\ ...,\ M$) are broken and cannot be used.

Answer the following form of $ Q $ queries:

• In the $ i $-th query, $ c_i $ and $ d_i $ are given. At this time, what is the minimum number of teleportation devices needed to move from city $ c_i $ to city $ d_i $ by transferring between devices?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_M $ $ b_M $ $ c_1 $ $ d_1 $ $ c_2 $ $ d_2 $ $ : $ $ c_Q $ $ d_Q $

Output Format

On the $ i $-th line, output the answer to the $ i $-th query. However, if it is impossible to move from city $ c_i $ to city $ d_i $ by transferring between teleportation devices, output -1 instead.

Sample Input and Output

Sample Input #1

6 7 4
1 2
2 4
2 5
2 6
3 5
3 6
5 6
1 2
2 3
5 6
2 5

Sample Output #1

2
1
2
3

Sample Input #2

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

Sample Output #2

1
-1

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ M\ \leq\ 10^5$
• $1\ \leq\ Q\ \leq\ 10^5$
• $1\ \leq\ a_i\ <\ b_i\ \leq\ N$
• There are no distinct pairs $i,\ j$ such that $a_i\ =\ a_j$ and $b_i\ =\ b_j$
• $1\ \leq\ c_i\ <\ d_i\ \leq\ N$

Sample Explanation 1

The usable teleportation devices are as shown in the figure below. Thick lines indicate that the teleportation device between the cities is usable, and dotted lines indicate that it is broken. 

见题面 Input 部分

见题面 Output 部分