Уравнения над словами
Вам дан текст T и шаблон P. Вы хотите проверить, можно ли стереть некоторые буквы T так, чтобы из оставшихся символов получить P. Например, слово programming можно частично стереть, чтобы получить pong или program или roaming (но не map, так как буквы должны оставаться в том же порядке). Оба слова состоят только из маленьких букв английского алфавита.
Имеется лишь одна загвоздка: текст T кодируется системой уравнений. В уравнениях используются специальные символы (каждый символ обозначается словом из заглавных букв), каждый из которых кодирует какое-то слово в алфавите {a, ..., z}. Каждое уравнение имеет одну из следующих форм:
A = слово над алфавитом {a,...,z}
или
A = B + C
где A, B, C могут быть любыми символами, а символ + означает конкатенацию слов. Система является:
недвусмысленной – для фиксированного символа A имеется в точности одно уравнение с A в левой части;
ациклической – если Вы начинаете с любого символа A, делаете подстановки в соответствии с уравнениями, и никогда не сможете получить выражение, содержащее A снова.
Такая система всегда имеет единственное решение. Например, в системе:
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
символ START кодирует слово goodtimesbadtimes.
Имея одно слово P в качестве шаблона, систему уравнений и один конкретный начальный символ S этой системы, определите, присутствует ли шаблон P в слове, закодированном S.
Входные данные
Первая строка содержит количество тестов t. Описания тестов приведены ниже:
Каждый тест начинается со строки, содержащей одно целое число k (1 ≤ k ≤ 500) - количество уравнений. Следующие k строк содержат уравнения. Каждый из них имеет одну из двух форм, указанных в условии задачи, с пробелами, разделяющими слова, знаками плюс и знаками уравнений. Каждое слово (включая имена символов) имеет длину не менее одного и не более пяти символов.
Следующая строка содержит один специальный символ (слово заглавными буквами), а заключительная строка содержит непустое слово, содержащее не более 2000 строчных букв. Это начальный символ и шаблон для поиска соответственно.
Выходные данные
Для каждого теста выведите ответ в отдельной строке: YES если шаблон присутствует в заданном слове, и NO в противном случае.