Description

森林大学为学生开设了 $\mathbf{N}$ 门课程，想要获得学位，必须修完所有课程。课程只能一次上一门——你必须完成一门课程后才能开始另一门。每门课程要么是基础课程（即无任何先修要求），要么是进阶课程（此时恰好有一门其他课程作为它的先修课程）。

学生必须在修读某门课程前先修完其先修课程，虽然这两门课不必连续修读。一门课程可以是多门其他课程的先修课程。不存在先修关系的环路。任意一种满足先修关系的 $\mathbf{N}$ 门课程修读顺序，都是有效的毕业方案。

当你毕业时，学校会在你的毕业帽上印上你修读课程顺序的缩写。具体来说，这个缩写是一个字符串，按你修课顺序依次取每门课程名称的首字母。例如，如果你先修了 Coding 课，再修 Jamming 课，你的毕业帽上会写 CJ。有些“炫酷单词”作为毕业帽字符串的子串被认为很时髦。

请考虑所有满足先修关系的有效修课顺序。对于每个炫酷单词，你需要计算有多少比例的修课顺序，其毕业帽字符串包含该炫酷单词（至少一次）作为子串。注意，我们关注的是修课顺序的比例，而不是不同毕业帽字符串的比例。（因为多门课程可能首字母相同，实际可能的字符串种类比修课顺序种类少。）

这道题与 Code Jam 常规题目不同，只需给出近似答案；请特别注意输出格式。

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例组数。接下来有 $\mathbf{T}$ 组测试用例，每组包含以下五行：

1. 一个整数 $\mathbf{N}$，表示课程数。
2. $\mathbf{N}$ 个整数，第 $i$ 个数表示第 $i$ 门课程的先修课程编号，若为 0 则表示该课程为基础课程。课程编号为 1 到 $\mathbf{N}$。
3. $\mathbf{N}$ 个大写英文字母（中间无空格），第 $i$ 个字母为第 $i$ 门课程名称的首字母。
4. 一个整数 $\mathbf{M}$，表示炫酷单词的数量。
5. $\mathbf{M}$ 个炫酷单词，每个由大写英文字母组成。

Output Format

对于每组测试用例，输出一行 Case #x: $y_1$ $y_2$ ... $y_{\mathbf{M}}$，其中 $\mathrm{x}$ 是测试用例编号（从 1 开始），$y_i$ 表示第 $i$ 个炫酷单词作为子串出现在毕业帽字符串中的有效修课顺序比例。

若 $y_i$ 与正确答案的绝对误差不超过 0.03，即视为正确。详见 FAQ 关于什么格式的实数是可接受的说明。

2
2
0 1
CJ
4
CJ C D JC
3
0 1 0
BAA
3
AA AAB ABA

Case #1: 1.0 1.0 0.0 0.0
Case #2: 0.67 0.0 0.33

Hint

样例解释

样例输出展示了一组可接受答案，其他答案只要精度满足要求也可以。

在样例第 1 组中，课程 1（C）为基础课，是课程 2（J）的先修课。唯一的修课顺序是先修 1 再修 2，毕业帽字符串为 CJ。所以炫酷单词 CJ、C、D、JC 分别在 1、1、0、0 个有效顺序中出现，比例分别为 1、1、0、0。

在样例第 2 组中，基础课 1（B）是进阶课 2（A）的先修课，课程 3（A）也是基础课。共有三种修课顺序：

1. 先修 1，再修 2，再修 3（字符串：BAA）
2. 先修 1，再修 3，再修 2（字符串：BAA）
3. 先修 3，再修 1，再修 2（字符串：ABA）

炫酷单词 AA、AAB、ABA 分别在 2、0、1 个有效顺序中出现，比例分别为 2/3、0、1/3。

限制条件

小数据集（25 分，测试集 1 - 可见）

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{N} \leqslant 100$。
• $1 \leqslant \mathbf{M} \leqslant 5$。
• 每个炫酷单词长度 $1 \leqslant \text{len} \leqslant 20$。
• 每个炫酷单词只包含大写英文字母。
• 先修关系无环。

翻译由 GPT4.1 完成。