CF1045C.Hyperspace Highways

In an unspecified solar system, there are $N$ planets. A space government company has recently hired space contractors to build $M$ bidirectional Hyperspace™ highways, each connecting two different planets. The primary objective, which was to make sure that every planet can be reached from any other planet taking only Hyperspace™ highways, has been completely fulfilled. Unfortunately, lots of space contractors had friends and cousins in the Space Board of Directors of the company, so the company decided to do much more than just connecting all planets.

In order to make spending enormous amounts of space money for Hyperspace™ highways look neccessary, they decided to enforce a strict rule on the Hyperspace™ highway network: whenever there is a way to travel through some planets and return to the starting point without travelling through any planet twice, every pair of planets on the itinerary should be directly connected by a Hyperspace™ highway. In other words, the set of planets in every simple cycle induces a complete subgraph.

You are designing a Hyperspace™ navigational app, and the key technical problem you are facing is finding the minimal number of Hyperspace™ highways one needs to use to travel from planet $A$ to planet $B$. As this problem is too easy for Bubble Cup, here is a harder task: your program needs to do it for $Q$ pairs of planets.

在某个未指明的太阳系中，共有 $N$ 颗行星。一家太空政府公司最近聘请了太空承包商，修建了 $M$ 条双向“超空间™”高速公路，每条公路连接两颗不同的行星。最初的主要目标——确保任意两颗行星之间均可仅通过“超空间™”高速公路相互抵达——已完全实现。然而，由于大量太空承包商在该公司“太空董事会”中拥有朋友和表亲等关系，公司决定开展远超单纯连通所有行星的额外工程。

为了使在“超空间™”高速公路上投入巨额太空资金显得确有必要，公司对“超空间™”高速公路网络施加了一条严格规则：只要存在一条不重复经过任何行星、且能从某颗行星出发并最终返回该行星的旅行路径（即一个简单环），那么该路径上所经所有行星两两之间都必须直接由一条“超空间™”高速公路相连。换言之，每个简单环所包含的行星集合，必须构成一个完全子图。

你正在设计一款“超空间™”导航应用程序，当前面临的关键技术问题是：找出从行星 $A$ 到行星 $B$ 所需经过的最少“超空间™”高速公路数量。由于该问题对 Bubble Cup 竞赛而言过于简单，现给出一个更难的任务：你的程序需对 $Q$ 对行星分别求解上述最小值。

The first line contains three positive integers $N$ ($1\leq N\leq 100\,000$), $M$ ($1\leq M\leq 500\,000$) and $Q$ ($1\leq Q\leq 200\,000$), denoting the number of planets, the number of Hyperspace™ highways, and the number of queries, respectively.

Each of the following M lines contains a highway: highway $i$ is given by two integers $u_i$ and $v_i$ ($1 \leq u_i \lt v_i \leq N$), meaning the planets $u_i$ and $v_i$ are connected by a Hyperspace™ highway. It is guaranteed that the network of planets and Hyperspace™ highways forms a simple connected graph.

Each of the following $Q$ lines contains a query: query $j$ is given by two integers $a_j$ and $b_j$ $(1 \leq a_j \lt b_j \leq N )$, meaning we are interested in the minimal number of Hyperspace™ highways one needs to take to travel from planet $a_j$ to planet $b_j$.

第一行包含三个正整数 $N$（$1\leq N\leq 100\,000$）、$M$（$1\leq M\leq 500\,000$）和 $Q$（$1\leq Q\leq 200\,000$），分别表示行星的数量、超空间™高速公路的数量以及查询的数量。

接下来的 $M$ 行每行描述一条高速公路：第 $i$ 条高速公路由两个整数 $u_i$ 和 $v_i$（$1 \leq u_i \lt v_i \leq N$）给出，表示行星 $u_i$ 与行星 $v_i$ 之间存在一条超空间™高速公路。保证所有行星与超空间™高速公路构成一个简单连通图。

接下来的 $Q$ 行每行描述一个查询：第 $j$ 个查询由两个整数 $a_j$ 和 $b_j$（$1 \leq a_j \lt b_j \leq N$）给出，表示我们希望求出从行星 $a_j$ 到行星 $b_j$ 所需经过的最少超空间™高速公路数量。

Output $Q$ lines: the $j$-th line of output should contain the minimal number of Hyperspace™ highways one needs to take to travel from planet $a_j$ to planet $b_j$.

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

The graph from the second sample:

第二个样例的图：