시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 128 27 16 18.605%

문제

알파벳 소문자로 이루어진 단어 T와 패턴 P가 있다. 이 때, T에 문자를 적절히 삭제해서 P가 되는지 확인해보려고 한다.

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

T는 문자 방정식로 인코딩 되어있다. 이 방정식은 알파벳 대문자로 되어있는 변수를 사용한다.

모든 방정식은 다음과 같은 형태를 갖는다.

  • A = 알파벳 소문자로 이루어져 있는 단어 또는
  • A = B + C (B와 C는 모두 변수, +는 문자열 연결을 의미한다.)

또한, 어떤 변수가 왼쪽에 있는 경우는 단 한번만 나오며, A에 대한 방정식을 풀 때, 우변에 다시 A가 나오는 경우가 없다.

따라서, 이 방정식은 항상 유일한 해를 가진다. 예를 들어, 다음과 같은 방정식을 살펴보자.

  • 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개의 줄에는 방정식이 주어진다. 방정식은 위에서 설명한 2가지 형태 중 하나이고, 공백으로 구분되어져 있는 단어, +, =로만 이루어져 있다. 모든 단어와 변수의 이름은 최대 5글자이다. 다음 줄에는 어떤 변수가 T인지 주어진다. 그리고 마지막 줄에는 패턴 P가 주어진다. 

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

출력

각 테스트 케이스에 대해서, T의 문자를 적절히 삭제해서 P를 만들 수 있으면 YES를, 아니면 NO를 출력한다.

예제 입력

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

예제 출력

YES

힌트

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 2012 E번