题目描述

题目译自 XXVI Olimpiada Informatyczna – III etap Długie podróże

Bajtazar 在 25 年的信息学奥赛中结识了许多朋友，足迹遍布拜托城。然而，他的朋友分散在各地，探访颇为不易。拜托城有 $n$ 个城市，通过 $m$ 条双向航线连接，网络设计确保任意两城市间可达（通常需换乘）。

根据新交通法，每条航线票价固定为 $1$。Bajtazar 提出 $p$ 个问题：「从朋友所在城市 $s_i$ 飞到城市 $t_i$ 需要多少费用？」你希望帮助他规划最便宜的路线。

你注意到，Bajtazar 询问的朋友相距甚远，最短路线至少需 $\frac{n}{10}$ 次飞行。回答他的查询，助他在下届奥赛前探访所有朋友！

输入格式

第一行包含三个整数 $n, m, p$ $(2 \leq n \leq 100000, n-1 \leq m \leq 200000, 1 \leq p \leq 200000)$，分别表示城市数、航线数和查询数。城市编号为 $1$ 至 $n$。

接下来的 $m$ 行描述航线，第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示城市 $a_i$ 和 $b_i$ 间有双向航线。每条航线至多描述一次。

接下来的 $p$ 行描述查询，第 $i$ 行包含两个整数 $s_i, t_i$ $(1 \leq s_i, t_i \leq n, s_i \neq t_i)$，表示从城市 $s_i$ 到 $t_i$ 的最短飞行次数查询。保证每条路线费用至少 $\frac{n}{10}$。

输出格式

输出 $p$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个查询的最短飞行次数。

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

2
3

从城市 $2$ 到 $5$ 的最短路线为 $2 \rightarrow 4 \rightarrow 5$，需 $2$ 次飞行。从城市 $1$ 到 $6$ 的最短路线为 $1 \rightarrow 3 \rightarrow 4 \rightarrow 6$，需 $3$ 次飞行。

附加样例

1. $n=10, m=30, p=45$。
2. $n=100$，航线形成环。
3. $n=100000$，航线形成两个相接的环。

数据范围与提示

详细子任务附加限制及分值如下表所示。