P3633 [APIO2011] Guess the Word

“Guess the Word” is a two-player game popular among young students in Iran. Suppose there are two players, A and B. A moves first and secretly chooses a word from a corpus known to both players, remembering it in his mind. Then he draws a row of short dashes on a small piece of paper, as many as the number of letters in the word (say $n$ dashes). Next, B tries to guess the word. In each round, B chooses a letter and tells A. A responds according to the following rules: 1. If the letter B said appears in the word, A writes it on the corresponding dashes. If the entire word becomes complete (all letters have been guessed), B wins. 2. Otherwise, if the letter does not appear in the word, A writes it below the leftmost dash whose underneath is still blank. If all the positions below the dashes are already filled (that is, before this round, B has already guessed $n$ wrong letters), then B loses and A wins. For example, A chose the word RED from the corpus, and B has guessed the letters A, E, C, D, B, and R in order. The outcome of each step is shown below, and B wins in the end. But if B had guessed S instead of R in the last step, he would have lost. ```cpp - - - （第一步，B选A） A E - - - （第二步，B选E） A E - - - （第三步，B选C） A C E D - - - （第四步，B选D） A C E D - - - （第五步，B选B） A C B R E D - - - （第六步，B选R） A C B ``` Aidin is a fan of the Guess the Word game. He believes that if the given corpus is large enough and its words are “nice,” player A (the first mover) can take an unfair action—changing the chosen word. That is, since player A keeps the word only in his mind and does not write it down, he can change the word at any time during the game, as long as all current revealed information remains consistent. For example, in the game above, if the words RED, BED, LED, and TED are all in the corpus, then after the 4th move, A can be sure he will win. He will always write B’s letters under the dashes (i.e., treat them as wrong letters), so each time he loses at most one candidate from the set {RED, BED, LED, TED}. Finally, he will announce to B: “The word is, uh…,” and then name one of the remaining words in his set. Aidin wonders whether, if the corpus is good enough, A can even be certain of victory from the very beginning. For example, if the word length is 2 and all words in the set {ME, MD, DE, ED, AS, IS, AI, SI} are in the corpus, then A can always win. Please find a winning strategy for A yourself. Given a corpus, Aidin wants to know whether player A is guaranteed to win no matter how B plays. Note that at the end of any game, if A wins, A must be able to name a word from the corpus as the chosen word, and this word must be consistent with all of A’s responses.

The input contains several corpora, each of which should be processed independently. The first line contains an integer C, the number of corpora. Then C corpora follow, each as a separate module, and modules are separated by one empty line. 1 ≤ C ≤ 20. For each module, the first line contains a positive integer k, the number of words in the corpus. The next lines contain k words. Adjacent words are separated by spaces, tabs, or newlines. Each word consists of fewer than 7 uppercase English letters. Each word consists of distinct letters; that is, no letter appears more than once in a single word.

For each corpus, if player A has a guaranteed winning strategy (that is, no matter how B guesses, A can always win), output a line “Yes”. Otherwise, output a line “No”. Do not include quotes.

- For 20% of the testdata, k ≤ 100, and each word’s length is at most 3. - For 50% of the testdata, k ≤ 300, and each word’s length is at most 4. - For 100% of the testdata, k ≤ 1000. The input file is smaller than 500 KB. Translated by ChatGPT 5