CF1045C Hyperspace Highways

在一个未指明的太阳系中，有 $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™ 高速公路。保证所有行星和高速公路构成一个简单连通图。 接下来的 $Q$ 行，每行描述一个查询：第 $j$ 个查询由两个整数 $a_j$ 和 $b_j$（$1 \leq a_j < b_j \leq N$）给出，表示你需要求从行星 $a_j$ 到行星 $b_j$ 至少需要经过多少条 Hyperspace™ 高速公路。

输出 $Q$ 行，第 $j$ 行输出从行星 $a_j$ 到行星 $b_j$ 至少需要经过的 Hyperspace™ 高速公路数。

第二个样例中的图如下： 由 ChatGPT 4.1 翻译