A10870 | Expected diameter of a tree

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.

The first line contains three integers $n$ , $m$ and $q$ ( $1<=n,m,q<=10^{5}$ ) — 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.

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 .