문자 방정식

알파벳 소문자로 이루어진 문자열 T와 패턴 P가 있다. T에서 문자를 몇 개 지워서 P를 만들 수 있는지, 즉 P가 T의 부분 수열인지 판별하려고 한다.

예를 들어 단어 programming에서 문자를 적절히 지우면 pong, program, roaming 등을 얻을 수 있다. 다만 남은 문자들의 순서는 그대로 유지되어야 하므로 map은 만들 수 없다.

T는 대문자로 된 변수를 사용하는 문자 방정식으로 주어진다. 각 방정식은 다음 두 형태 중 하나이다.

• A = w : A는 소문자로 이루어진 단어 w이다.
• A = B + C : A는 두 변수 B와 C를 이어 붙인 문자열이다. (+는 문자열 연결을 뜻한다.)

각 변수는 방정식의 왼쪽에 최대 한 번만 나타나며, 어떤 변수의 정의를 따라가도 자기 자신이 다시 나오는 순환은 없다. 따라서 모든 변수의 값은 유일하게 정해진다.

예를 들어 다음 방정식을 살펴보자.

• START = FIRST + SECND
• FIRST = D + E
• SECND = F + E
• D = good
• E = times
• F = bad

이 방정식을 풀면 START = goodtimesbadtimes 이다.

패턴 P, 문자 방정식, 그리고 T에 해당하는 변수가 주어졌을 때, T에서 문자를 적절히 지워 P를 만들 수 있는지 판별하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

첫째 줄에 방정식의 개수 K (1 ≤ K ≤ 500)가 주어진다. 이어지는 K개의 줄에는 방정식이 한 줄에 하나씩 주어진다. 각 방정식은 위에서 설명한 두 형태 중 하나이며, 공백으로 구분된 단어와 +, = 로만 이루어진다. 모든 단어와 변수 이름의 길이는 최대 5글자이다. 그다음 줄에는 T에 해당하는 변수가 주어진다. 마지막 줄에는 패턴 P가 주어진다.

P의 길이는 최대 2,000이다.

각 테스트 케이스마다 T에서 문자를 적절히 지워 P를 만들 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.