P13362 [GCJ 2011 Qualification] Magicka

Magicka™ is an action-adventure game developed by Arrowhead Game Studios. In Magicka you play a wizard, invoking and combining elements to create Magicks. This problem has a similar idea, but it does not assume that you have played Magicka. Note: "invoke" means "call on." For this problem, it is a technical term and you don't need to know its normal English meaning. Magicka™ is a trademark of Paradox Interactive AB. Paradox Interactive AB does not endorse and has no involvement with Google Code Jam.

作为一名法师，你可以召唤八种元素，这些是“基础”元素。每个基础元素是 $\{Q, W, E, R, A, S, D, F\}$ 中的一个字符。当你召唤一个元素时，它会被添加到你的元素列表的末尾。例如：如果你先召唤 $W$，再召唤 $A$（我们简称为“召唤 $WA$”），那么你的元素列表将变为 $[W, A]$。 我们会指定一些基础元素对，这些元素对可以组合成非基础元素（其余 18 个大写字母）。例如，$Q$ 和 $F$ 可以组合成 $T$。如果某一时刻，这对元素出现在元素列表的末尾，那么这两个元素会被立即移除，并用它们组合成的新元素替换。例如，如果元素列表为 $[A, Q, F]$ 或 $[A, F, Q]$，那么它会变为 $[A, T]$。 我们还会指定一些基础元素对，它们彼此“对立”。当你召唤一个元素后，如果它没有立即与其他元素组合成新元素，并且它与元素列表中的某个元素是对立的，那么你的整个元素列表会被清空。 例如，假设 $Q$ 和 $F$ 组合成 $T$，$R$ 和 $F$ 是对立的。那么依次召唤以下元素（从左到右）会有如下结果： - $QF \rightarrow [T]$（$Q$ 和 $F$ 组合成 $T$） - $QEF \rightarrow [Q, E, F]$（$Q$ 和 $F$ 没有同时出现在末尾，无法组合） - $RFE \rightarrow [E]$（$F$ 和 $R$ 对立，列表被清空，然后召唤 $E$） - $REF \rightarrow []$（$F$ 和 $R$ 对立，列表被清空） - $RQF \rightarrow [R, T]$（$QF$ 组合成 $T$，列表不会被清空） - $RFQ \rightarrow [Q]$（$F$ 和 $R$ 对立，列表被清空） 给定一系列要召唤的元素，最终你的元素列表中会有哪些元素？

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据由一行组成，内容如下，元素之间用空格分隔： 首先是一个整数 $C$，接着是 $C$ 个字符串，每个字符串有三个字符：前两个是基础元素，第三个是它们组合成的非基础元素。接下来是一个整数 $D$，然后是 $D$ 个字符串，每个字符串有两个字符，表示这两个基础元素是对立的。最后是一个整数 $N$，接着是一个长度为 $N$ 的字符串，表示你要依次召唤的基础元素（从左到右依次召唤）。

对于每个测试用例，输出一行，格式为“Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最终元素列表，格式为“$[e_0, e_1, \dots]$”，其中 $e_i$ 是最终元素列表中的第 $i$ 个元素。具体格式请参考样例输出。

**数据范围** - $1 \leq T \leq 100$。 - 每对基础元素最多只会出现在一个组合中，但它们既可以组合也可以对立。 - 没有基础元素会与自身对立。 - 与游戏 Magicka 不同，元素列表长度没有限制。 **小数据集（10 分，测试点 1 - 可见）** - $0 \leq C \leq 1$。 - $0 \leq D \leq 1$。 - $1 \leq N \leq 10$。 - 时间限制：3 秒。 **大数据集（15 分，测试点 2 - 隐藏）** - $0 \leq C \leq 36$。 - $0 \leq D \leq 28$。 - $1 \leq N \leq 100$。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译