Expected diameter of a tree
Contest: Codeforces Round 411 (Div. 1)
Difficulty rating: 2500
Tags: binary search, brute force, dfs and similar, dp, sortings, trees

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 $$a \in V$$ and some vertex in $$b \in U$$ 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 format:
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 ui and vi (1 ≤ ui, vi ≤ n), that means there is an edge between vertices ui and vi.

It is guaranteed that the given graph is a forest.

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

Output format:
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 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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 $${ \frac { 3 + 3 + 2 } { 3 } } \approx 2. 6 6 6 6 6 6 6 6 6$$.

Example input:
3 1 2
1 3
3 1
2 3

Example output:
-1
2.0000000000

Example input:
5 2 3
2 4
4 3
4 2
4 1
2 5

Example output:
-1
2.6666666667
2.6666666667

Editorial:
Let's solve the problem for two trees.
Define dt as diameter of t-th tree and fti as the maximum path starting from i-th vertex of t-th tree, for all valid i and j, assume that the edge is between them and find the diameter with max(f1i + f2j + 1, max(d1, d2)).
The answer will be:
Let's improve the $${\mathcal {O}}(n^{2})$$ solution to $${ \mathcal { O } } ( n \cdot \log { ( n ) } )$$.
Let's sort the arrays f1 and f2 decreasingly and make two partial sums of them, p1 and p2, such that $$p_{t_i} = \sum_{j=1}^{i-1} f_{t_j}$$. Iterate on ft, in step i, we will check all of the valid edges which i-th vertex is an endpoint of that: Consider the first element in f1 - t as j such that fti + f(1 - t)j > max(d1, d2), by binary search, according to the previous solution for i-th step, we should add it to the answer:
Let's prove if in each query, we choose t, the smaller tree, the solution will be accepted.
There is two simple modes we should consider:
1- If $$\min(sz_1,sz_2) < \sqrt{n}$$: The time complexity will be $${ \mathcal { O } } ( { \sqrt { ( n ) } } \cdot \log ( n ) )$$ per query.
2- If $$\min(sz_1,sz_2)\geq \sqrt{n}$$: Number of trees with $$sz \geq \sqrt{n}$$ is at last $$\sqrt{(n)}$$. If we don't calculate the answer for two same pairs of vertices by memoization, at last $$\sqrt{(n)}$$ time we need to these bigger trees, so it yields $${ \mathcal { O } } ( \sum s z _ { i } \cdot { \sqrt { ( n ) } } \cdot \log ( n ) ) = { \mathcal { O } } ( n \cdot { \sqrt { ( n ) } } \cdot \log ( n ) )$$.