#2664. [BeiJing wc2012]孵化者

“我要将有关魔法和奇迹的一切，封印于卡片之中！”
“这个心愿„„要是这个心愿能够实现„„”
“对，这样你我都将化为卡片！”
 
现在，孵化者被封印在了一张卡片里。这张卡片的效果是：可以使一张魔法
卡片变为两张（可能是其他类型的）魔法卡片。显然，它是非常珍贵且有价值的
卡片。
 
我们接下来要关注的是一个以它为背景的，用于训练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，分别判定这个规则
和串所对应的游戏是否有解。

样例输入

			
  2 1 

  A->a 

  B->b 

  S->AB 

  ab 

  cd 

样例输出

			
YES 

NO