English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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 .
[samples]
## Note
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 .
Pasha 是一名优秀的学生，也是 MoJaK 最好的朋友之一。他总是有需要思考的问题。今天，他们讨论了以下问题：
我们有一个森林（无环无向图），包含 #cf_span[n] 个顶点和 #cf_span[m] 条边。我们需要回答 #cf_span[q] 个查询。每个查询给出两个顶点 #cf_span[v] 和 #cf_span[u]。令 #cf_span[V] 为包含 #cf_span[v] 的连通分量中的顶点集合，#cf_span[U] 为包含 #cf_span[u] 的连通分量中的顶点集合。现在，我们从 #cf_span[V] 中选择一个顶点，从 #cf_span[U] 中选择一个顶点，并在这两个顶点之间添加一条边，然后计算所得连通分量的值 #cf_span[d]。如果所得连通分量是一棵树，则 #cf_span[d] 为该连通分量的 _直径_；否则，#cf_span[d] 等于 _-1_。如果我们从集合中均匀随机选择顶点 #cf_span[a] 和 #cf_span[b]，那么 #cf_span[d] 的期望值是多少？
你能帮助 Pasha 解决这个问题吗？
连通分量的 _直径_ 是该连通分量中某对顶点之间的最大 _距离_。两个顶点之间的 _距离_ 是连接它们的路径上边数的最小值。
注意：查询不会向初始森林添加边。
第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[q]（#cf_span[1 ≤ n, m, q ≤ 105]）——顶点数、图中的边数和查询数。
接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]），表示顶点 #cf_span[ui] 和 #cf_span[vi] 之间有一条边。
保证给定的图是一个森林。
接下来的 #cf_span[q] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]）——第 #cf_span[i] 个查询给出的两个顶点。
对于每个查询，输出如题所述的 #cf_span[d] 的期望值。
你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。假设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，当 时，评测程序将判定你的答案正确。
在第一个例子中，顶点 #cf_span[1] 和 #cf_span[3] 属于同一连通分量，因此第一个查询的答案为 _-1_。对于第二个查询，有两种添加边的方案：一种是添加边 #cf_span[1 - 2]，另一种是添加边 #cf_span[2 - 3]。两种情况下所得直径均为 #cf_span[2]，因此答案为 #cf_span[2]。
在第二个例子中，第一个查询的答案显然是 _-1_。第二个查询的答案是三种情况的平均值：当添加边 #cf_span[1 - 2] 或 #cf_span[1 - 3] 时，直径为 #cf_span[3]；当添加边 #cf_span[1 - 4] 时，直径为 #cf_span[2]。因此，答案为 。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[q]（#cf_span[1 ≤ n, m, q ≤ 105]）——顶点数、图中的边数和查询数。接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]），表示顶点 #cf_span[ui] 和 #cf_span[vi] 之间有一条边。保证给定的图是一个森林。接下来的 #cf_span[q] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]）——第 #cf_span[i] 个查询给出的两个顶点。
## Output
对于每个查询，输出如题所述的 #cf_span[d] 的期望值。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。假设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，当 时，评测程序将判定你的答案正确。
[samples]
## Note
在第一个例子中，顶点 #cf_span[1] 和 #cf_span[3] 属于同一连通分量，因此第一个查询的答案为 _-1_。对于第二个查询，有两种添加边的方案：一种是添加边 #cf_span[1 - 2]，另一种是添加边 #cf_span[2 - 3]。两种情况下所得直径均为 #cf_span[2]，因此答案为 #cf_span[2]。在第二个例子中，第一个查询的答案显然是 _-1_。第二个查询的答案是三种情况的平均值：当添加边 #cf_span[1 - 2] 或 #cf_span[1 - 3] 时，直径为 #cf_span[3]；当添加边 #cf_span[1 - 4] 时，直径为 #cf_span[2]。因此，答案为 。
**Definitions**
Let $ G = (V, E) $ be a forest with $ n = |V| $ vertices and $ m = |E| $ edges.
Let $ \mathcal{C} = \{C_1, C_2, \dots, C_k\} $ be the set of connected components of $ G $, where each $ C_i $ is a tree.
For each component $ C_i $, let:
- $ |C_i| $ denote its number of vertices,
- $ \text{diam}(C_i) $ denote its diameter (maximum distance between any two vertices),
- $ \text{ecc}(v) $ denote the eccentricity of vertex $ v \in C_i $ (maximum distance from $ v $ to any other vertex in $ C_i $),
- $ \text{radius}(C_i) = \min_{v \in C_i} \text{ecc}(v) $,
- $ \text{center}(C_i) $ be the set of vertices achieving the radius.
For any two distinct components $ C_i $ and $ C_j $, define:
$$
d_{\text{new}}(C_i, C_j) = \text{diam}(C_i), \text{diam}(C_j), \max_{u \in C_i, v \in C_j} \left( \text{ecc}_{C_i}(u) + 1 + \text{ecc}_{C_j}(v) \right)
$$
The diameter of the merged component $ C_i \cup C_j $ when connecting $ u \in C_i $ and $ v \in C_j $ is:
$$
\max\left( \text{diam}(C_i), \text{diam}(C_j), \text{ecc}_{C_i}(u) + 1 + \text{ecc}_{C_j}(v) \right)
$$
**Constraints**
1. $ 1 \le n, m, q \le 10^5 $
2. $ G $ is a forest (acyclic undirected graph).
3. Each query provides two vertices $ u, v $.
4. Let $ C_u $ be the component containing $ u $, $ C_v $ the component containing $ v $.
- If $ C_u = C_v $, output $ -1 $.
- Otherwise, let $ S_u = C_u $, $ S_v = C_v $.
**Objective**
For each query $ (u, v) $ with $ C_u \ne C_v $:
Compute the expected value of the diameter of $ C_u \cup C_v $ after adding a uniformly random edge between a vertex in $ C_u $ and a vertex in $ C_v $:
$$
\mathbb{E}[d] = \frac{1}{|C_u| \cdot |C_v|} \sum_{a \in C_u} \sum_{b \in C_v} \max\left( \text{diam}(C_u), \text{diam}(C_v), \text{ecc}_{C_u}(a) + 1 + \text{ecc}_{C_v}(b) \right)
$$
Output this expected value with absolute or relative error $ \le 10^{-6} $.
API Response (JSON)
{
"problem": {
"name": "D. Expected diameter of a tree",
"description": {
"content": "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 _",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF804D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n\nWe have a forest (acyclic undirected graph) with _...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Pasha 是一名优秀的学生，也是 MoJaK 最好的朋友之一。他总是有需要思考的问题。今天，他们讨论了以下问题：\n\n我们有一个森林（无环无向图），包含 #cf_span[n] 个顶点和 #cf_span[m] 条边。我们需要回答 #cf_span[q] 个查询。每个查询给出两个顶点 #cf_span[v] 和 #cf_span[u]。令 #cf_span[V] 为包含 #cf_span[v] 的...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be a forest with $ n = |V| $ vertices and $ m = |E| $ edges. \nLet $ \\mathcal{C} = \\{C_1, C_2, \\dots, C_k\\} $ be the set of connected components of $ G $, where ea...",
"is_translate": false,
"language": "Formal"
}
]
}