Essay Writing

Interview

Time limit1sMemory limit128 MB

Summary

Given a sample text, two keywords, and a target length w, decide whether a word sequence of exactly w words exists where every adjacent pair appears in the sample and both keywords occur at least once.

Level: Medium6 of 10
Topics: Graph, BFS, Shortest path, Bit manipulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

2
4 5 solution answers
when you program your solution correctly the
program will work and
it will write right answers for you but when you are wrong
it will not
4 6 solution answers
when you program your solution correctly the
program will work and
it will write right answers for you but when you are wrong
it will not

Expected output

Data Set 1:
No
Data Set 2:
Yes

Example 2

Input

1
1 2 hello world
hello world

Expected output

Data Set 1:
Yes

Example 3

Input

1
1 3 cat fish
cat sat on

Expected output

Data Set 1:
No