说明

给定一个文本 $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。

1
6
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
START
debate

YES