Essay Writing

It is one thing to make a computer speed up your math homework by solving a linear system for you, but writing essays? Well, if your teacher is not looking too closely, you can actually do something with computers, based on Markov models. By analyzing example text you can learn which words tend to follow which other words in English, and then generate random text using those rules. The result looks surprisingly similar to English, especially if you consider which word follows a given sequence of two preceding words.

Suppose your computer has already analyzed English for you. Now you have to write a final essay. Obviously you do not want completely random text; you would rather have the text contain certain key terms related to the topic. Here you will write a program that tests whether an essay of a given length can be generated so that it contains two given keywords.

More formally, you are given some sample text, two keywords, and a target length $w$. Using only the words that appear in the sample text, you must decide whether it is possible to produce a sequence of exactly $w$ words such that:

• The sequence contains each of the two keywords at least once (in any order).
• Every word except the first must directly follow the word before it at least once in the sample text (that is, the two words appear consecutively, in that order, on the same line of the sample).
• The first word of the sequence may be any word that appears in the sample text.

Decide whether such a sequence exists.

The first line contains an integer $K \ge 1$, the number of data sets. It is followed by $K$ data sets of the form below.

The first line of a data set contains two integers $n$ and $w$, followed by two words $s_1$ and $s_2$. Here $w \le 100$ is the number of words the essay must contain, $s_1$ and $s_2$ are the two required keywords, and $1 \le n \le 10$ is the number of lines of sample text to learn from.

This is followed by $n$ lines, each containing a sequence of 1 to 20 words. Every word (both here and above) is a string of 1 to 20 lower-case letters. Words are separated by one or more spaces. There is no punctuation or any other character.

For each data set, first print a line Data Set x:, where $x$ is the number of the data set (starting from 1). On the next line print Yes if a matching essay can be generated, or No otherwise.