{"raw_statement":[{"iden":"statement","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 _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?\n\nCan you help Pasha to solve this problem?\n\nThe _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.\n\nNote that queries don't add edges to the initial forest."},{"iden":"input","content":"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.\n\nEach 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_.\n\nIt is guaranteed that the given graph is a forest.\n\nEach 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."},{"iden":"output","content":"For each query print the expected value of _d_ as described in the problem statement.\n\nYour 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 ."},{"iden":"examples","content":"Input\n\n3 1 2\n1 3\n3 1\n2 3\n\nOutput\n\n\\-1\n2.0000000000\n\nInput\n\n5 2 3\n2 4\n4 3\n4 2\n4 1\n2 5\n\nOutput\n\n\\-1\n2.6666666667\n2.6666666667"},{"iden":"note","content":"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.\n\nIn 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 ."}],"translated_statement":[{"iden":"statement","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] 的连通分量中的顶点集合，#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] 的期望值是多少？\n\n你能帮助 Pasha 解决这个问题吗？\n\n连通分量的 _直径_ 是该连通分量中某对顶点之间的最大 _距离_。两个顶点之间的 _距离_ 是连接它们的路径上边数的最小值。\n\n注意：查询不会向初始森林添加边。\n\n第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[q]（#cf_span[1 ≤ n, m, q ≤ 105]）——顶点数、图中的边数和查询数。\n\n接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]），表示顶点 #cf_span[ui] 和 #cf_span[vi] 之间有一条边。\n\n保证给定的图是一个森林。\n\n接下来的 #cf_span[q] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]）——第 #cf_span[i] 个查询给出的两个顶点。\n\n对于每个查询，输出如题所述的 #cf_span[d] 的期望值。\n\n你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。假设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，当  时，评测程序将判定你的答案正确。\n\n在第一个例子中，顶点 #cf_span[1] 和 #cf_span[3] 属于同一连通分量，因此第一个查询的答案为 _-1_。对于第二个查询，有两种添加边的方案：一种是添加边 #cf_span[1 - 2]，另一种是添加边 #cf_span[2 - 3]。两种情况下所得直径均为 #cf_span[2]，因此答案为 #cf_span[2]。\n\n在第二个例子中，第一个查询的答案显然是 _-1_。第二个查询的答案是三种情况的平均值：当添加边 #cf_span[1 - 2] 或 #cf_span[1 - 3] 时，直径为 #cf_span[3]；当添加边 #cf_span[1 - 4] 时，直径为 #cf_span[2]。因此，答案为 。"},{"iden":"input","content":"第一行包含三个整数 #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] 个查询给出的两个顶点。"},{"iden":"output","content":"对于每个查询，输出如题所述的 #cf_span[d] 的期望值。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。假设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]，当  时，评测程序将判定你的答案正确。"},{"iden":"examples","content":"输入3 1 21 33 12 3输出-12.0000000000输入5 2 32 44 34 24 12 5输出-12.66666666672.6666666667"},{"iden":"note","content":"在第一个例子中，顶点 #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]。因此，答案为 。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 each $ C_i $ is a tree.  \nFor each component $ C_i $, let:  \n- $ |C_i| $ denote its number of vertices,  \n- $ \\text{diam}(C_i) $ denote its diameter (maximum distance between any two vertices),  \n- $ \\text{ecc}(v) $ denote the eccentricity of vertex $ v \\in C_i $ (maximum distance from $ v $ to any other vertex in $ C_i $),  \n- $ \\text{radius}(C_i) = \\min_{v \\in C_i} \\text{ecc}(v) $,  \n- $ \\text{center}(C_i) $ be the set of vertices achieving the radius.  \n\nFor any two distinct components $ C_i $ and $ C_j $, define:  \n$$\nd_{\\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)\n$$  \nThe diameter of the merged component $ C_i \\cup C_j $ when connecting $ u \\in C_i $ and $ v \\in C_j $ is:  \n$$\n\\max\\left( \\text{diam}(C_i), \\text{diam}(C_j), \\text{ecc}_{C_i}(u) + 1 + \\text{ecc}_{C_j}(v) \\right)\n$$\n\n**Constraints**  \n1. $ 1 \\le n, m, q \\le 10^5 $  \n2. $ G $ is a forest (acyclic undirected graph).  \n3. Each query provides two vertices $ u, v $.  \n4. Let $ C_u $ be the component containing $ u $, $ C_v $ the component containing $ v $.  \n   - If $ C_u = C_v $, output $ -1 $.  \n   - Otherwise, let $ S_u = C_u $, $ S_v = C_v $.  \n\n**Objective**  \nFor each query $ (u, v) $ with $ C_u \\ne C_v $:  \nCompute 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 $:  \n$$\n\\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)\n$$  \nOutput this expected value with absolute or relative error $ \\le 10^{-6} $.","simple_statement":null,"has_page_source":false}