Pasha 是一名好学生,也是 MoJaK 最好的朋友之一。他总是有一个问题需要思考。今天他们讨论了以下问题。
我们有一个有 n 个顶点和 m 个边的森林(非循环无向图)。我们需要回答 q 个问题。在每个查询中,给出两个顶点 v 和 u。令 V 为包含 v 的图的连通分量中的顶点集合,U 为包含 u 的图的连通分量中的顶点集合。让我们在 V$$ 中的某个顶点 $$a \in V$$ 和 U$$ 中的 $$b \in U$$ 中的某个顶点之间添加一条边,并计算结果分量的值 d。如果生成的组件是一棵树,则值 d 是组件的直径,否则等于 -1。如果我们从集合中均匀随机选择顶点 a 和 b,d 的期望值是多少?
你能帮助Pasha解决这个问题吗?
组件的直径是组件中某对顶点之间的最大距离。两个顶点之间的距离是两个顶点之间的某些路径上边的最小数量。
请注意,查询不会向初始林添加边。
输入
第一行包含三个整数 n、m 和 q(1 ≤ n, m, q ≤ 105) — 图中的顶点数、边数和查询数。
接下来的 m 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n),这意味着顶点 ui 和 vi 之间有一条边。
保证给定的图是一个森林。
接下来的 q 行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n) - 第 i 个查询中给出的顶点。
输出
对于每个查询,打印问题陈述中所述的 d 的预期值。
如果您的答案的绝对或相对误差不超过 10 - 6,则认为您的答案是正确的。假设您的答案是 a,陪审团的答案是 b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
3 1 2 1 3 3 1 2 3
输出 #1
-1 2.0000000000
输入 #2
5 2 3 2 4 4 3 4 2 4 1 2 5
输出 #2
-1 2.6666666667 2.6666666667
注意
在第一个示例中,顶点 1 和 3 位于同一组件中,因此第一个查询的答案为 -1。对于第二个查询,有两种添加边的选项:一种是添加边 1 - 2,另一种是 2 - 3。这两种方式的结果直径都是 2,所以答案是 2。
在第二个示例中,第一个查询的答案显然是 -1。第二个查询的答案是三种情况的平均值:对于添加的边 1 - 2 或 1 - 3,直径为 3,对于添加的边 1 - 4,直径为 2。因此,答案为 $${ \frac { 3 + 3 + 2 } { 3 } } \approx 2。 6 6 6 6 6 6 6 6 6$$。