题目背景

备注：原题（Java）时间限制 3.0s，空间限制 512 MB。

题目描述

小明国庆节准备去某星系进行星际旅行，这个星系里一共有 $n$ 个星球，其中布置了 $m$ 道双向传送门，第 $i$ 道传送门可以连接 $a_i$，$b_i$ 两颗星球（$a_i \neq b_i$ 且任意两颗星球之间最多只有一个传送门）。

他看中了一款 “旅游盲盒”，一共有 $Q$ 个盲盒，第 $i$ 个盲盒里的旅行方案规定了旅行的起始星球 $x_i$ 和最多可以使用传送门的次数 $y_i$。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。

小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买，他想知道能旅行到的不同星球的数量的期望是多少。

输入格式

输入共 $m + Q + 1$ 行。

第一行为三个正整数 $n, m, Q$。

后面 $m$ 行，每行两个正整数 $a_i$，$b_i$。

后面 $Q$ 行，每行两个整数 $x_i$，$y_i$。

输出格式

输出共一行，一个浮点数（四舍五入保留两位小数）。

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

2.00

提示

【样例解释】

• 第一个盲盒可以旅行到 $1, 2, 3$。
• 第二个盲盒可以旅行到 $2$。
• 第三个盲盒可以旅行到 $1, 2$。

所以期望是 $(3 + 1 + 2) / 3 = 2.00$。

【数据范围】

• 对于 $20 \%$ 的评测用例，保证 $n \leq 300$。
• 对于 $100 \%$ 的评测用例，保证 $n \leq 1000$，$m \leq \min \left\{\dfrac{n(n - 1)}{2}, 5n\right\}$，$Q \leq 50000$，$0 \leq y_i \leq n$，$1 \leq x_i \leq n$。