에세이 작성

컴퓨터로 연립방정식을 풀어 수학 숙제를 빨리 끝내는 것과, 컴퓨터로 에세이를 쓰는 것은 전혀 다른 이야기처럼 보인다. 하지만 선생님이 아주 꼼꼼히 살펴보지 않는다면, 마르코프 모델(Markov model)을 이용해 실제로 무언가를 해 볼 수 있다. 예시 문장들을 분석하면 영어에서 어떤 단어 뒤에 어떤 단어가 자주 오는지 배울 수 있고, 그 규칙을 이용해 무작위 텍스트를 생성할 수 있다. 이렇게 만든 텍스트는 놀라울 만큼 영어처럼 보이며, 특히 바로 앞의 두 단어 뒤에 어떤 단어가 오는지를 함께 고려하면 더욱 그렇다.

이미 컴퓨터가 영어를 분석해 두었다고 하자. 이제 기말 에세이를 써야 한다. 완전히 무작위인 텍스트는 원하지 않고, 주제와 관련된 특정 핵심 단어가 반드시 들어가기를 바란다. 이 문제에서는 주어진 길이의 에세이를 두 개의 필수 단어를 포함하도록 생성할 수 있는지 판별하는 프로그램을 작성한다.

좀 더 정확히 말하면, 예시 텍스트와 두 개의 단어, 그리고 목표 길이 $w$가 주어진다. 예시 텍스트에 등장하는 단어들만 사용하여, 다음 조건을 모두 만족하는 정확히 $w$개의 단어로 이루어진 수열을 만들 수 있는지 판별해야 한다.

• 수열은 두 필수 단어를 각각 최소 한 번씩 포함한다(순서는 상관없다).
• 첫 단어를 제외한 모든 단어는, 예시 텍스트에서 바로 앞 단어 뒤에 적어도 한 번은 연달아 등장한 적이 있어야 한다(즉 두 단어가 같은 줄에서 그 순서대로 이웃하여 나타난 적이 있어야 한다).
• 수열의 첫 단어는 예시 텍스트에 등장하는 어떤 단어여도 된다.

이러한 수열이 존재하는지 출력하라.

첫 줄에는 데이터 집합의 개수 $K \ge 1$이 주어진다. 이어서 아래 형식의 데이터 집합이 $K$개 주어진다.

각 데이터 집합의 첫 줄에는 두 정수 $n$과 $w$, 그리고 두 단어 $s_1$, $s_2$가 주어진다. 여기서 $w \le 100$은 에세이가 포함해야 하는 단어의 개수, $s_1$과 $s_2$는 두 필수 단어, $1 \le n \le 10$은 학습에 사용할 예시 텍스트의 줄 수이다.

그 뒤로 $n$개의 줄이 이어지며, 각 줄에는 1개에서 20개 사이의 단어가 들어 있다. (위의 단어들을 포함해) 모든 단어는 1자에서 20자 사이의 소문자 알파벳으로 이루어진 문자열이다. 단어는 하나 이상의 공백으로 구분된다. 구두점이나 다른 문자는 없다.

각 데이터 집합에 대해, 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이다(1부터 시작). 다음 줄에 조건을 만족하는 에세이를 생성할 수 있으면 Yes, 그렇지 않으면 No를 출력한다.