[BeiJing wc2012]孵化者

时间限制：3s 空间限制：128MB

题目描述

“我要将有关魔法和奇迹的一切，封印于卡片之中！”
“这个心愿„„要是这个心愿能够实现„„”
“对，这样你我都将化为卡片！”

现在，孵化者被封印在了一张卡片里。这张卡片的效果是：可以使一张魔法
卡片变为两张（可能是其他类型的）魔法卡片。显然，它是非常珍贵且有价值的
卡片。

我们接下来要关注的是一个以它为背景的，用于训练SpellCard的使用技巧，
以及：体现了孵化者无与伦比的再生能力的单人卡片游戏，叫做《Incubator》。

游戏的道具是一些卡片，分为两类，一类是 Spell，一类是 Witch。我们用大
写字母’A’、’B’、„„来表示不同的 Spell，用小写字母’a’、’b’、„„来表示不同
的 Witch。
游戏用到两个牌堆，我们称它们为 S 堆和 W 堆，S 堆中只可能有 Spell，W
堆中只可能有 Witch。
游戏开始时，S 堆仅有一张卡片’S’，而 W堆中会有若干张卡片，我们把这个
信息用一个字符串 w来表示，其中 w的首个字符对应 W堆顶部的卡片，w的下
一个字符对应 W堆从上向下数第二张卡片（如果有的话），依次类推。
游戏的目标是进行操作，使得这两个牌堆都变成空的，一共有两种操作：
    1. 使用魔法消灭 Witch：
      如果S 堆顶部的Spell克制 W堆顶部的 Witch 才可以进行。
      使用后，这两张卡片都被移除。
    2. 使用Incubator 进行孵化：
      如果S 堆非空就可以进行。
      需要依照某一孵化规则。
将S堆顶部的卡片移除，由孵化规则在S堆顶部加入两张新的卡片。

这个游戏一共有N1个克制关系以及 N2个孵化规则。
每一个“克制”关系由一个字符串给出，例如： “A->a”表示’A’克制’a’。
每一个孵化规则也由一个字符串给出，例如： “S->AB” ，表示可以将’S’从堆
顶移除，之后加入’A’和’B’，其中’A’在’B’的上面。

在给定规则以及串 w的情形下，如果存在一个有限多步就可以使得两牌堆均
为空的操作方法，那么我们称：这个游戏是有解的。

你的任务是：给定规则以及 T个串：w1、w2、„„、wT，分别判定这个规则
和串所对应的游戏是否有解。

输入格式

第一行一共有两个正整数：N1、N2。
接下来 N1行，每行一个串，表示一个克制关系。
接下来 N2行，每行一个串，表示一个孵化规则。
接下来 T 行，每行一个串 wi。

输出格式

一共输出 T行：
每行为“YES”或“NO”（不包含引号），表示对应的串和规则组成的游戏是
否是有解的。（有解则输出“YES”，否则输出“NO”）

样例输入

  2 1 
  A->a 
  B->b 
  S->AB 
  ab 
  cd

样例输出

YES 
NO

提示

对于100%的数据： 1≤ N1≤20， 1 ≤ N2≤20， 1 ≤ |wi|≤ 20， 1≤ T≤100。
保证所有的克制关系串都是合法的，即具有“A->a”的形式，其中 A 是某
个大写字母，a 是某个小写字母。
保证所有的孵化规则串都是合法的，即具有“S->AB”的形式，其中 S、A、
B是某些大写字母，它们可以相同。
“->”是一个长度为 2 的串，其首个字符的 ASCII 码为 45，下一个字符的
ASCII 码为62 （均是在十进制下），这个符号也是 C++中的 Structure dereference。
保证串 wi仅包含小写字母。

题目来源

没有写明来源