P15480 [CERC2012] Word equations

给定一个文本 $T$ 和一个模式 $P$。你需要判断是否可以通过删除 $T$ 中的一些字母，使得剩下的字符恰好构成 $P$。例如，单词 programming 可以通过部分删除得到 pong、program 或 roaming（但不能得到 map，因为字母必须保持原有顺序）。两个单词仅由英文字母的小写字母组成。 但有一个难点：文本 $T$ 是由一个方程系统编码的。这些方程使用特殊符号（每个符号由一个大写字母组成的单词表示），每个符号编码一个由字母 `a` 到 `z` 构成的单词。每个方程具有以下两种形式之一： - $\operatorname{A}$ = 一个由 `a` 到 `z` 组成的单词 - $\operatorname{A}=\operatorname{B}+\operatorname{C}$ 其中 $\operatorname{A}$、$\operatorname{B}$、$\operatorname{C}$ 可以是任意特殊符号，`+` 表示单词的连接。该系统具有以下性质： - **无歧义**：对于每个固定符号 $\operatorname{A}$，有且仅有一个以 $\operatorname{A}$ 为左端的方程； - **无环**：从任意符号 $\operatorname{A}$ 出发，根据方程进行代入（将左端替换为右端），永远不会再次得到包含 $\operatorname{A}$ 的表达式。 这样的系统总有唯一解。例如，在以下系统中： - $\operatorname{START}=\operatorname{FIRST}+\operatorname{SECND}$ - $\operatorname{FIRST}=\operatorname{D}+\operatorname{E}$ - $\operatorname{SECND}=\operatorname{F}+\operatorname{E}$ - $\operatorname{D}=$`good` - $\operatorname{E}=$`times` - $\operatorname{F}=$`bad` 符号 $\operatorname{START}$ 编码的单词是 `goodtimesbadtimes`。 给定一个作为模式的单词 $P$、一个方程系统以及该系统的一个特定起始符号 $S$，判断模式 $P$ 是否出现在 $S$ 所编码的单词中。

输入的第一行包含测试用例的数量 $T$。随后是每个测试用例的描述： 每个测试用例以一行整数 $k$（$1\le k\le 500$）开头，表示方程的数量。接下来 $k$ 行包含方程。每行具有题目陈述中给出的两种形式之一，单词、加号和等号之间用空格分隔。每个单词（包括符号名称）长度至少为 1，至多为 5。 下一行包含一个单独的特殊符号（一个大写字母组成的单词），最后一行包含一个非空且长度不超过 2000 的小写字母单词。它们分别是起始符号和待查找的模式。

按照输入中出现的顺序输出每个测试用例的答案。每个测试用例输出一行：如果模式出现在给定的编码单词中，则输出 `YES`，否则输出 `NO`。