在波兰信息学奥林匹克竞赛的 25 年历程中，Byteasar 结识了许多朋友。在周年纪念之际，他希望能拜访所有的朋友，这意味着他需要再次游历 Byteotia。不过这一次，Byteasar 计划乘飞机出行。Byteotia 有 $n$ 个城镇，每个城镇都有自己的机场。有 $m$ 条直接连接城镇的双向航线，航线网络的设计保证了任意两个城镇之间都可以通过转机到达。

Byteasar 以节俭著称，他希望尽可能降低旅行成本。作为一名经验丰富的旅行者，他原本已经做好了所有规划，但一项新的基础设施法案将任何直飞国内航班的价格固定为 1 个 Bythaler。这改变了一切，现在 Byteasar 正为 $p$ 个问题而苦恼，这些问题的形式为：“从住在城镇 $s_i$ 的朋友那里飞往住在城镇 $t_i$ 的朋友那里需要花费多少钱？”请帮他找出最便宜的航线。

你注意到 Byteasar 询问的朋友居住地相距较远——具体来说，对于每一对朋友，连接他们的每条路径都至少包含 $\frac{n}{10}$ 次飞行。请回答 Byteasar 的询问，以便他有机会在下一届奥林匹克竞赛之前拜访他所有的朋友！

输入格式

标准输入的第一行包含三个整数 $n, m, p$ ($2 \le n \le 100\,000, n - 1 \le m \le 200\,000, 1 \le p \le 200\,000$)，用空格分隔，分别表示城镇数量、航线数量和询问次数。城镇编号从 $1$ 到 $n$。

接下来的 $m$ 行描述航线；第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，用空格分隔，表示城镇 $a_i$ 和 $b_i$ 之间存在一条双向航线。每条航线最多在输入中描述一次。

接下来的 $p$ 行包含询问；第 $i$ 行包含两个整数 $s_i, t_i$ ($1 \le s_i, t_i \le n, s_i \neq t_i$)，用空格分隔，表示询问从城镇 $s_i$ 到城镇 $t_i$ 的价格（即最短路径上的飞行次数）。已知每个询问的价格至少为 $\frac{n}{10}$ Bythaler。

输出格式

你的程序应向标准输出打印 $p$ 行；第 $i$ 行应包含一个整数：第 $i$ 个询问的答案。

样例

输入格式 1

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

输出格式 1

2
3

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试点。