P17323 [ICPC 2018 Nanjing R] Frank

Frank 喜欢旅行。然而，他并不喜欢完全规划好的旅程。相反，他热衷于在城市之间随机旅行。 Frank 最喜欢的国家是喵国（Country Meow），因为该国的道路十分复杂。 喵国有 $N$ 座城市，编号从 $0$ 到 $N-1$，并且有 $M$ 条单向道路。第 $i$ 条道路可以表示为 $(a_i, b_i)$，意味着它从城市 $a_i$ 出发，到达城市 $b_i$，途中不经过任何其他城市。有趣的是，可能存在 $a_i=b_i$ 的道路，或者若干条起点和终点完全相同的道路。道路的修建方式保证了对于任意两座城市 $A$ 与 $B$，人们都可以通过这些道路从 $A$ 抵达 $B$。 Frank 正计划着 $Q$ 次前往喵国的旅行。每次旅行计划是一个有序的城市列表 $C=(c_0, c_1, \cdots, c_{K-1})$，并且对于所有 $0 \le i \le K-2$ 满足 $c_i \neq c_{i+1}$。 在一次依照计划 $C$ 的旅行中，Frank 将： 1. 前往城市 $c_0$。 2. 从所有起点为 Frank 当前所在城市的道路中，均匀随机地选择一条。 3. 沿着所选道路前往下一座城市。 4. 如果 $C$ 是当前已访问城市序列的一个子序列，那么此次旅行结束。否则，回到步骤 2。 （若可以通过从序列 $B$ 中删除若干（或不删除）元素且不改变顺序而得到序列 $A$，则称 $A$ 是 $B$ 的一个子序列。） 然而，每条道路需收取 $1$ 美元的通行费。Frank 想知道他在每次旅行中所花费总费用的期望值。你能帮帮他吗？

第一行包含三个正整数 $N, M, Q$ ($3 \le N \le 400$, $M \le 4 \times 10^5$, $Q \le 400$)。 接下来的 $M$ 行描述喵国的道路。每行包含两个整数 $a_i, b_i$ ($0 \le a_i, b_i < N$) —— 第 $i$ 条道路的起点和终点城市。 再接下来的 $2Q$ 行描述 Frank 制定的旅行计划。每两行描述一个计划。第一行包含一个整数 $K$ ($2 \le K \le 500$) —— 城市列表的长度；第二行包含 $K$ 个整数 $c_0, c_1, \cdots, c_{K-1}$ ($0 \le c_i < N$, $c_i \neq c_{i+1}$) —— 该计划中的城市列表。

对于每个计划，在一行中输出一个实数 —— 对应旅行花费总费用的期望值。 若你的输出中每个数与裁判答案中相应数的绝对误差或相对误差不超过 $10^{-8}$，则你的答案被视为正确。形式化地说，设你的答案为 $a$，裁判的答案为 $b$，若 $\frac{|a - b|}{\max(1, |b|)} \le 10^{-8}$，则你的答案被视为正确。 保证对于任何计划，答案均小于 $10^7$。

翻译由 DeepSeek V4 Pro 完成