Interstellar Travel Expectation

During the National Day holiday, Xiao Ming plans an interstellar journey in a certain galaxy. This galaxy contains \(n\) planets and \(m\) bidirectional teleporters. The \(i\)th teleporter connects planet \(a_i\) and planet \(b_i\) (with \(a_i \neq b_i\) and at most one teleporter connecting any two planets).

Xiao Ming is interested in a "travel blind box". There are \(Q\) blind boxes. The \(i\)th blind box specifies a travel plan starting from planet \(x_i\) and allows using teleporters at most \(y_i\) times. In each travel plan, all planets that can be reached from \(x_i\) using at most \(y_i\) teleporter usages are considered available for travel. Note that the starting planet is always counted as reachable.

Since Xiao Ming will buy one blind box at random, he wishes to know the expected number of distinct planets he can travel to. In other words, if \(c_i\) denotes the number of reachable planets for the \(i\)th blind box, then you should compute:

[ E = \frac{1}{Q} \sum_{i=1}^{Q} c_i. ]

Compute and output the expected number \(E\) as a real number. Your output will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq 10^5, 0 \leq m \leq 10^5)\), representing the number of planets and teleporters respectively.

The next \(m\) lines each contain two integers \(a_i\) and \(b_i\) \((1 \leq a_i, b_i \leq n, a_i \neq b_i)\), describing a bidirectional teleporter connecting planets \(a_i\) and \(b_i\). It is guaranteed that there is at most one teleporter between any two planets.

The following line contains an integer \(Q\) \((1 \leq Q \leq 10^5)\), the number of blind boxes.

Then \(Q\) lines follow, each containing two integers \(x_i\) and \(y_i\) \((1 \leq x_i \leq n, 0 \leq y_i \leq 10^5)\), representing the starting planet and the maximum number of teleporter usages allowed in the \(i\)th travel plan.

outputFormat

Output a single real number, the expected number of planets that can be reached, i.e., \(E\). Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

sample

4 3
1 2
2 3
3 4
2
1 1
2 2

3.000000