题目描述

给定一篇文章 $T$ 和一个单词 $P$，你希望知道是否可以通过从 $T$ 中删除一些字母得到 $P$。

比如，单词 $\text{programming}$ 可以得到 $\text{pong}$ 或者 $\text{program}$ 或者 $\text{roaming}$，但是得不到 $\text{map}$。

保证所有单词只包含英文小写字母。

然而文章 $T$ 通过一种等价形式进行了加密。

等式使用一些特殊的符号（由大写字母组成），每个符号都用来表示一个由小写字母组成的单词。每个等式都满足下面之一的形式：

$A =$ 由小写字母组成的单词或 $A = B + C$。

其中 $A$， $B$， $C$ 可以表示任何特殊的符号，而 $+$ 号表示单词的拼接。

这种等价形式是：

明确的 $-$ 对于每个固定的符号 $A$，只有一个 $A$ 在等式的左边（$A$ 在左边只出现一次）。

无环的 $-$ 如果你从任意的符号 $A$ 开始做等价替换，你永远不会得到一个替换过 $A$ 的表达式还包含 $A$。

这样的等价形式总是只有唯一解。例如，当等价形式是这样的：

$\text{START = FIRST + SECND}$

$\text{FIRST = D + E}$

$\text{SECND = F + E}$

$\text{D = good}$

$\text{E = times}$

$\text{F = bad}$

则符号 $\text{START}$ 加密了单词 $\text{goodtimesbadtimes}$。

给定一个单词 $P$，一些等式，和一个特别的符号 $S$，请你计算 $S$ 所加密的单词是否能得到 $P$。

输入格式

第一行一个正整数 $T$，表示有 $T$ 组数据。

每组数据第一行有一个正整数 $k$，表示有 $k$ 个等式。

接下来 $k$ 行，每行一个等式，等式里的字符串由空格隔开，每个字符串长度不超过 $5$。

接下来一行包含一个特殊符号 $S$（一个大写字母组成的单词）。

再接下来一行包含一个非空的由小写字母组成的单词 $P$。

输出格式

对于每组数据输出一行，若能，输出 YES，否则输出 NO。

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

YES

数据规模与约定

对于 $100\%$ 的数据满足，$1 \le k \le 500$，每个等式内字符串长度不超过 $5$，$P$ 的长度不超过 $2000$。