시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB3621100.000%

문제

"단어 추측(GMW, Guess My Word)" 게임은 젊은 이란 학생들 사이에서 널리 유행하는 두 사람이 하는 게임이다. 게임의 두 참가자를 A와 B라 하자. A가 두 사람 모두 알고 있는 말뭉치에서 단어를 하나 임의로 선택하여 기억한다. 그리고는 종이 위에 단어의 문자 수(n) 만큼의 수평 선분을 한 줄에 그린다. 그 후 종이를 둘 사이에 둔다.

이제는 B가 이 단어가 무엇인지 문자들을 차례로 추측하여 맞추어야 한다. 각 단계에서 B 는 하나의 문자를 선택하고, 그것을 A에게 말한다. 이에 대해,

  • B가 말한 문자가 그 단어에 있을 경우, A는 해당하는 선분 위의 적절한 위치에 이 문자를 쓴다. 만약 단어가 완성되면 (단어의 모든 문자가 쓰여 지면) B가 이긴다!
  • 그렇지 않으면 즉, 말한 문자가 단어에 없으면, A는 빈 공간으로 남아있는 가장 왼쪽 선분 아래에 그 문자를 쓴다. 만약 모든 선분 아래의 공간이 모두 차있어 그 문자를 쓸 수 없으면(즉, B가 벌써 n개의 틀린 문자를 말했다면) B가 지고, A가 이기게 된다. 이 경우에, A는 이긴 후, 자기가 선택한 단어를 B에게 밝혀야 한다.

예를 들어, A가 말뭉치로부터 단어 RED를 선택했다고 하고, B는 차례대로 A, E, C, D, B, R을 말했다고 하자. 각 단계의 결과는 아래의 그림과 같고, 최종 승리자는 B가 된다. 그러나, 만약 마지막 단계에서 B가 R대신 S를 추측했다면, B가 지게 된다.

Aidin은 GMW 게임을 아주 좋아한다. 그는 생각하기를 주어진 말뭉치가 충분히 크고, 상대적으로 좋은 단어들로 구성되어 있으면, A는 단어를 바꾸는 부당한 행동을 할 수 있을 것이라고 생각한다. 그것은, A가 마음으로만 단어를 생각하고 있고 어디에도 기록해놓은 상태가 아니기 때문에, 게임 도중에 현재까지 주어진 답과 일관성이 있는 다른 단어로 바꿀 수 있다. 예를 들어, 앞에서 언급한 게임에서 만약 말뭉치에 RED, BED, LED, 그리고 TED가 들어있다면, 4번째 단계 후에 A는 게임에서 이길 수 있음을 확신할 수 있다. B가 선택한 문자를 A는 선분 아래에 (틀렸다는 의미로) 항상 쓸 수 있고, B는 계속된 단계에서 {RED, BED, LED, TED}의 단어들 중 맞출 수 없는 단어가 적어도 하나가 있다. 마지막에 그는 B 에게 다음과 같이 말할 수 있다. " 그 단어는 음……", 그는 집합에서 남아있는 단어를 하나 말하면 된다.

A가 좋은 말뭉치를 가지면, 경우에 따라서 참가자 A가 이길 수 있을 것이라고 Aidin은 생각한다. 예를 들어, 만약 2글자 단어로 게임을 하는데 집합 {ME, MD, DE, ED, AS, IS, AI, SI}에 있는 모든 단어들을 말뭉치에서 찾을 수 있다면, A는 언제나 이길 수 있다. 그 전략을 찾아라!

말뭉치가 주어졌을 때, B의 모든 선택에 대해서 A가 확실히 이길 수 있는지 혹은 그렇지 않은지를 Aidin은 알고 싶어 한다.

입력

입력은 독립적으로 풀어야 하는 여러 개의 말뭉치로 구성되어 있다.

입력의 첫 번째 줄에는 말뭉치의 수 C가 주어진다. 그리고, 이 C개의 말뭉치의 정보가 그 다음 줄부터 C개의 블록으로 주어진다. C는 1이상 20이하 정수이다.

각 말뭉치들의 첫 번째 줄에는 말뭉치의 단어수를 나타내는 하나의 정수 K가 주어진다. 그 다음 줄부터는 K개의 서로 다른 단어가 빈칸들 혹은 탭들(tabs) 그리고/혹은 줄 바꿈 기호들을 사이에 두고 주어진다. 모든 단어들은 영어의 대문자이고 단어의 길이는 항상 7보다 적다. 말뭉치의 각 단어에 있는 문자들은 모두 다르다. 즉, 하나의 단어에 두 번 이상 나오는 문자는 없다. 

입력 파일의 크기는 500KB 보다 작다.

모든 테스트 케이스에서 말뭉치의 단어의 수는 1,000개를 넘지 않는다.

출력

각 말뭉치에 대해서 만약 A가 이기는 전략이 존재하면(즉, B가 선택하는 문자들에 상관없이 언제나 이길 수 있으면) "Yes"를 출력한다. 그렇지 않으면 한 줄에 "No"를 출력한다.

A가 이기는 어떠한 게임이든지 마지막에는 B에게 말뭉치에 있는 단어가 선택된 단어로 주어져야 하고, 이는 게임을 하는 동안 A의 모든 답변과 일치하여야 한다.

예제 입력 1

2
12
SI ME AND AI ARE MD AS WHEN ED IS DE
HARPY

5
A B AB	AC AD

예제 출력 1

Yes
No

출처

Olympiad > Asia-Pacific Informatics Olympiad > APIO 2011 3번

  • 문제의 오타를 찾은 사람: yclock