Background

Note: In the original problem (Java), the time limit is 3.0 s and the memory limit is 512 MB.

Problem Description

Xiaoming plans to take an interstellar trip to a certain star system during the National Day holiday. There are $n$ planets in this star system, and $m$ bidirectional portals are set up. The $i$-th portal connects planets $a_i$ and $b_i$ ($a_i \neq b_i$, and between any two planets there is at most one portal).

He is interested in a “travel blind box”. There are $Q$ blind boxes in total. The travel plan in the $i$-th blind box specifies the starting planet $x_i$ and the maximum number of portal uses $y_i$. Starting from the given planet, all planets that can be reached using portals no more than the allowed number of times can be visited.

Xiaoming cares about how many planets can be visited under each plan. He can only randomly choose one blind box to buy, and he wants to know the expected number of different planets he can visit.

Input Format

There are $m + Q + 1$ lines of input.

The first line contains three positive integers $n, m, Q$.

The next $m$ lines each contain two positive integers $a_i, b_i$.

The next $Q$ lines each contain two integers $x_i, y_i$.

Output Format

Output one line containing a floating-point number (rounded to two decimal places).

3 2 3
1 2
2 3
2 1
2 0
1 1

2.00

Hint

[Sample Explanation]

• The first blind box can visit $1, 2, 3$.
• The second blind box can visit $2$.
• The third blind box can visit $1, 2$.

So the expectation is $(3 + 1 + 2) / 3 = 2.00$.

[Constraints]

• For $20\%$ of the test cases, $n \leq 300$ is guaranteed.
• For $100\%$ of the test cases, $n \leq 1000$, $m \leq \min \left\{\dfrac{n(n - 1)}{2}, 5n\right\}$, $Q \leq 50000$, $0 \leq y_i \leq n$, and $1 \leq x_i \leq n$ are guaranteed.

Translated by ChatGPT 5