← 返回题目列表

Codeforces · 1045/C

C. 超空间高速公路

中文机器翻译题面 查看原题

在一个未指定的太阳系中,有 $$$N$$$ 行星。一家太空政府公司最近聘请了太空承包商来建造 $$$M$$$ 双向 Hyperspace™ 高速公路,每条高速公路都连接两个不同的星球。主要目标是确保仅通过 Hyperspace™ 高速公路就可以从任何其他行星到达每个行星。不幸的是,许多太空承包商在公司的太空董事会中都有朋友和表兄弟,因此公司决定做的不仅仅是连接所有行星。

为了让花费巨额太空资金建设Hyperspace™高速公路显得有必要,他们决定对Hyperspace™高速公路网络实施严格的规定:只要有一条路可以穿越一些行星并返回起点而不需要穿越任何行星两次,行程中的每一对行星都应该由Hyperspace™高速公路直接连接。换句话说,每个简单周期中的行星集合都会产生一个完整的子图。

您正在设计一款 Hyperspace™ 导航应用程序,您面临的关键技术问题是找到从 $$$A$$$ 行星到 $$$B$$$ 行星所需的最少数量的 Hyperspace™ 高速公路。由于这个问题对于 Bubble Cup 来说太简单了,因此这是一个更困难的任务:您的程序需要为 $$$Q$$$ 对行星执行此任务。

输入

第一行包含三个正整数 $$$N$$$ ($$$1\leq N\leq 100\,000$$$)、$$$M$$$ ($$$1\leq M\leq 500\,000$$$) 和 $$$Q$$$ ($$$1\leq Q\leq 200\,000$$$),分别表示行星数量、Hyperspace™ 高速公路数量和查询数量。

以下 M 行中的每一行都包含一条高速公路:高速公路 $$$i$$$ 由两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i < v_i \leq N$$$) 给出,这意味着行星 $$$u_i$$$ 和 $$$v_i$$$ 通过 Hyperspace™ 高速公路连接。保证行星网络和 Hyperspace™ 高速公路形成一个简单的连通图。

以下 $$$Q$$$ 行中的每一行都包含一个查询:查询 $$$j$$$ 由两个整数 $$$a_j$$$ 和 $$$b_j$$$ $$$(1 \leq a_j < b_j \leq N )$$$ 给出,这意味着我们感兴趣的是从 $$$a_j$$$ 星球到 $$$a_j$$$ 行星所需的最少数量的 Hyperspace™ 高速公路行星$$$b_j$$$。

输出

输出 $$$Q$$$ 行:输出的第 $$$j$$$ 行应包含从行星 $$$a_j$$$ 到行星 $$$b_j$$$ 所需的最少数量的 Hyperspace™ 高速公路。

示例

输入 #1

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

输出 #1

1
2

输入 #2

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

输出 #2

2
2
3
3

注意

第二个样本的图表: