APIO '11 P3 - Guess My Word!

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

The official test data is incorrect and has been recreated. If there are any issues with the data, please contact Pookmeister on slack.

"Guess My Word" (or shortly GMW) is a two-player game, which is being played widely among young Iranian students! Naming two players A and B, initially A, the first player, picks a word from a corpus known to both players and keeps it in mind. Then, on a piece of paper visible to B, he draws as many little horizontal line segments as the number of letters in the word (say n) in a row.

Now B tries to guess the word, letter by letter. For each turn, B chooses a single letter and tells A. In response:

  • If the letter chosen by B occurs in the word, A writes it in the proper position above the respective line segment. If the word is completed (all of its letters are written), B wins!
  • Otherwise, if the letter does not occur in the word, player A writes it below the leftmost line segment that has an empty space below it. If A cannot write the letter because all spaces below the lines are occupied (i.e. B has already told n wrong letters) then B is lost and A is the winner! A has to reveal the chosen word to B in this case, after his win.

As an example consider A has picked the word RED (from the corpus), and B has guessed and told the letters A, E, C, D, B and R in consecutive turns. The result of each step is illustrated in the following figure. B is the final winner. But if B had guessed S instead of R in his last turn, he would have lost!

Aidin is a fan of the GMW game! He believes that if the given corpus is large enough and contains relatively good words, then player A (the starting player) can perform the unfair action of changing his Word! Since player A is just keeping the word in mind and does not write it anywhere, he is able to change it during the game to another word, which is also consistent to all of the responses given to B so far. For example, in the example game above, if the words RED, BED, LED and TED were available in the corpus, then A could guarantee a win after step 4. He would always write B's chosen letter below the line (meaning a wrong letter) and in each subsequent turn he would lose at most one of the words in the set \{RED, BED, LED, TED\}. At the end, he would announce to B: "the word was, umm\dots," he would just say the remaining word in his virtual set!

Aidin thinks that with a good corpus, player A can sometimes be guaranteed to win from the beginning! For example if they play with 2-letter words and all the words in set \{ME, MD, DE, ED, AS, IS, AI, SI\} can be found in the corpus; then A can always win. Find the strategy by yourself!

Given the corpus, Aidin wants to know whether player A can be sure to win against any strategy by B.

Input

Input consists of several corpora, which are to be solved independently.

The first line of the input consists of an integer C, the number of corpora. Then these C corpora come in C blocks below it. You can assume that 1 \le C \le 20.

The first line of each corpus consists of an integer K, the number of words in the corpus. The following lines consist of K words, separated by spaces, tabs, and/or line-breaks. All the words are written in English uppercase letters and their length is always less than seven. Each word in corpus has unique letters, (i.e. no letter is repeated in a single word more than once).

Output

For each corpus, write Yes if player A has a winning strategy (i.e. can always win regardless of the letters chose, and strategy decided by B). Otherwise, write No in a single line.

Remember that at the end of any game in which player A wins, player B needs to be given a word from the corpus as the Selected word, which is consistent with all responses of player A during the game!

Constraints

  • It is guaranteed that no corpus contains less than 1 or more than 1000 words.
  • In 20\% of the test cases, all of the words in all the given corpora contain at most 3 letters, and each corpus will have at most 100 words.
  • In 50\% of the test cases, the words will consist of at most 4 letters, and each corpus will have at most 300 words.

Sample Input

2
12
SI ME AND AI ARE MD AS WHEN ED IS DE HARPY
5
A B AB AC AD

Sample Output

Yes
No

Comments

There are no comments at the moment.