CF804D.Expected diameter of a tree

Pasha is a good student and one of MoJaK's best friends. He always have a problem to think about. Today they had a talk about the following problem.

We have a forest (acyclic undirected graph) with n vertices and m edges. There are q queries we should answer. In each query two vertices v and u are given. Let V be the set of vertices in the connected component of the graph that contains v, and U be the set of vertices in the connected component of the graph that contains u. Let's add an edge between some vertex and some vertex in and compute the value d of the resulting component. If the resulting component is a tree, the value d is the diameter of the component, and it is equal to -1 otherwise. What is the expected value of d, if we choose vertices a and b from the sets uniformly at random?

Can you help Pasha to solve this problem?

The diameter of the component is the maximum distance among some pair of vertices in the component. The distance between two vertices is the minimum number of edges on some path between the two vertices.

Note that queries don't add edges to the initial forest.

帕沙是一名优秀的学生，也是莫贾克最好的朋友之一。他总是有一些问题需要思考。今天，他们讨论了如下问题：

我们有一个包含 $n$ 个顶点和 $m$ 条边的森林（即无环无向图）。需要回答 $q$ 个查询。在每个查询中，给定两个顶点 $v$ 和 $u$。设 $V$ 为图中包含 $v$ 的连通分量内的所有顶点构成的集合，$U$ 为图中包含 $u$ 的连通分量内的所有顶点构成的集合。现在，在某个顶点 （属于 $V$）与某个顶点 （属于 $U$）之间添加一条边，并计算所得连通分量的值 $d$。若所得连通分量是一棵树，则 $d$ 为其直径；否则 $d = -1$。若从集合 $V$ 和 $U$ 中分别均匀随机地选取顶点 $a$ 和 $b$，那么 $d$ 的期望值是多少？

你能帮助帕沙解决这个问题吗？

该连通分量的直径定义为其中任意一对顶点之间的最大距离。两个顶点之间的距离定义为连接它们的某条路径上所含边数的最小值。

注意：这些查询不会向原始森林中实际添加边。

The first line contains three integers n, m and q(1 ≤ n, m, q ≤ 105) — the number of vertices, the number of edges in the graph and the number of queries.

Each of the next m lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n), that means there is an edge between vertices u__i and v__i.

It is guaranteed that the given graph is a forest.

Each of the next q lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n) — the vertices given in the i-th query.

第一行包含三个整数 $n$、$m$ 和 $q$（$1 ≤ n, m, q ≤ 10^5$）—— 分别表示图中顶点的数量、边的数量以及查询的数量。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 ≤ u_i, v_i ≤ n$），表示顶点 $u_i$ 与 $v_i$ 之间存在一条边。

保证给定的图是一片森林（即若干互不连通的树组成的无环无向图）。

接下来的 $q$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 ≤ u_i, v_i ≤ n$）—— 表示第 $i$ 个查询所给定的两个顶点。

For each query print the expected value of d as described in the problem statement.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. Let's assume that your answer is a, and the jury's answer is b. The checker program will consider your answer correct, if .

对于每个查询，请输出题目描述中所述的 $ d $ 的期望值。

若你的答案的绝对或相对误差不超过 $ 10^{-6} $，则视为正确。假设你的答案为 $ a $，评测组的答案为 $ b $。当满足 时，评测程序将判定你的答案正确。

In the first example the vertices 1 and 3 are in the same component, so the answer for the first query is -1. For the second query there are two options to add the edge: one option is to add the edge 1 - 2, the other one is 2 - 3. In both ways the resulting diameter is 2, so the answer is 2.

In the second example the answer for the first query is obviously -1. The answer for the second query is the average of three cases: for added edges 1 - 2 or 1 - 3 the diameter is 3, and for added edge 1 - 4 the diameter is 2. Thus, the answer is .

在第一个例子中，顶点 1 和 3 位于同一连通分量中，因此第一个查询的答案为 $-1$。对于第二个查询，添加边有两种选择：一种是添加边 $1\text{-}2$，另一种是添加边 $2\text{-}3$。在这两种情况下，所得图的直径均为 $2$，因此答案为 $2$。

在第二个例子中，第一个查询的答案显然为 $-1$。第二个查询的答案是三种情况的平均值：当添加边 $1\text{-}2$ 或 $1\text{-}3$ 时，直径为 $3$；当添加边 $1\text{-}4$ 时，直径为 $2$。因此，答案为 。