[Cerc2012]Word equations

时间限制:40s    【提交】    空间限制:128MB

题目描述

给定一篇文章T和一个单词P,你希望知道是否可以通过从T中删除一些字母得到P。比如,单词programming可以得到pong或者program或者roaming,但是得不到map。保证所有单词只包含英文小写字母。

然而文章T通过一种等价形式进行了加密。等式使用一些特殊的符号(由大写字母组成),每个符号都用来表示一个由小写字母组成的单词。每个等式都满足下面之一的形式:
A = 由小写字母组成的单词
A = B + C
其中A, B, C可以表示任何特殊的符号,而 + 号表示单词的拼接。这种等价形式是:
明确的——对于每个固定的符号A,只有一个A在等式的左边(A在左边只出现一次)。
无环的——如果你从任意的符号A开始做等价替换,你永远不会得到一个替换过A的表达式还包含A。
这样的等价形式总是只有唯一解。例如,当等价形式是这样的:
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
则符号START加密了单词goodtimesbadtimes。
给定一个单词P,一些等式,和一个特别的符号S,请你计算S所加密的单词是否能得到P。


输入格式

第一行一个正整数T,表示有T组数据。每组数据第一行有一个正整数k,表示有k个等式,1 <= k <= 500。接下来k行,每行一个等式,等式里的字符串由空格隔开,每个字符串长度不超过5。接下来一行包含一个特殊符号S(一个大写字母组成的单词)。再接下来一行包含一个非空的由小写字母组成的单词P,P的长度不超过2000。


输出格式

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


样例输入

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

样例输出

YES

提示

没有写明提示


题目来源

鸣谢Tjz