← 返回题目列表

Codeforces · 804/D

D. 树的预期直径

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

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$$。