TopCoder

User's AC Ratio

0.0% (0/6)

Submission's AC Ratio

0.0% (0/39)

Tags

Description

"猜單詞"是一個雙人遊戲,在伊朗的青年學生中廣為流行。
假設有兩個遊戲者A 和B,A 作為先手,首先在一個雙方都知道的語料庫中選出一個單詞,並記在腦海中。
隨後,他在一張小紙片上劃下與單詞字母數相等的小橫線(不妨設為 n 條)。
接下來,B嘗試猜出這個單詞。每一輪,B選擇一個字母並告訴A。 A 按如下規則回應:

※若B 所說的字母在單詞中出現,A就把它寫在對應的橫線上。如果整個單詞已經完整(所有的字母已經被猜出),B獲勝。
※否則,如果字母沒有在單詞中出現,A就把它寫在最左側的下方仍為空白的橫線下。
如果所有橫線下的空白處都已經有字母(也就是說,在這一輪前B已經猜了n個錯誤字母),那麼B就輸了,A獲勝。

例如,A 從語料庫中選出了單詞RED,且B 已經依次猜了字母A, E, C, D, B和 R。
每一步的結果都在下圖中展現。最終B獲勝。但如果B在最後一步猜了S而不是R,他就輸了。

Aidin 是猜單詞遊戲迷。他相信,如果給定的語料庫足夠大,且其中的單詞相對好,
那麼玩家A(先手)可以採取一種不公平的行動——修改選擇的單詞。
也就是說,既然玩家A只將單詞記在腦海中而不寫下來,那他能夠在遊戲過程中隨時變化這個單詞,
只要使得和當前已經給出的結果仍然一致即可。

例如,在上面的遊戲中,如果單詞RED, BED, LED 和TED 都在語料庫中,那麼在第4步之後,A就可以確信他將勝利。
他將總是把B給出的字母寫在橫線下(也就是認定其為錯誤的字母),
那麼每一次他將至多在集合{RED, BED, LED, TED} 中失去一個備選單詞。
最終他將向B 宣布:「這個單詞是,嗯,...」,然後在他的集合中說出一個剩下的單詞。

Aidin 想,如果語料庫足夠好,那麼A 甚至可能在遊戲一開始就確定獲勝。
例如,如果選擇的單詞長度為2,而集合{ME, MD, DE, ED, AS, IS, AI, SI}中的單詞都在語料庫中,
那麼A總能獲勝。請自己找出A獲勝的策略。

給定一個語料庫,Aidin 想知道是否無論B如何進行遊戲,玩家A 一定能獲勝?
請注意在任何一次遊戲結束時,
如果A獲勝,A需要能夠給出一個語料庫中的單詞作為被選出的單詞,這個單詞應當與A 所有給出的回答一致。

Input Format

輸入包含若干個語料庫。每個語料庫應該被獨立地處理。
輸入的第一行是一個整數C,代表語料庫的數目。隨後C個語料庫以C個模塊的形式出現在輸入中。
每兩個模塊之間以一個空行隔開。 1 ≤ C ≤ 20。

對於每個輸入模塊,第一行包含一個正整數k,表示語料庫中單詞的個數。
接下來的若干行中包含 k 個單詞。
相鄰的單詞以空格、製表符或換行符分隔。每個單詞由小於7 個大寫英語字母組成。
每個單詞都由不同的字母組成,也就是說,同一個字母在一個單詞中出現的次數不會超過 1 次。

對於20%的測試數據,k ≤ 100,每個單詞的長度不超過3;
對於50%的測試數據,k ≤ 300,每個單詞的長度不超過4;
對於所有測試數據中,k ≤ 1000。

Output Format

對於每個語料庫,如果玩家A 有必勝策略(也就是說,不論B 按什麼方法猜,A 總能獲勝),
輸出一行"Yes"。否則輸出一行"No"。輸出不包含引號。

Sample Input 1

2

12
SI ME AND AI ARE MD AS WHEN ED IS DE
HARPY

5
A B AB AC AD

Sample Output 1

Yes
No

Hints

Problem Source

原TIOJ1750 / APIO '11

Subtasks

No. Testdata Range Score
1 0 3
2 1 3
3 2 3
4 3 3
5 4 3
6 5 3
7 6 3
8 7 3
9 8 3
10 9 3
11 10 3
12 11 3
13 12 3
14 13 3
15 14 3
16 15 3
17 16 3
18 17 3
19 18 3
20 19 3
21 20 3
22 21 3
23 22 3
24 23 3
25 24 3
26 25 3
27 26 3
28 27 3
29 28 3
30 29 13

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 30000 65536 262144 1
1 30000 65536 262144 2
2 30000 65536 262144 3
3 30000 65536 262144 4
4 30000 65536 262144 5
5 30000 65536 262144 6
6 30000 65536 262144 7
7 30000 65536 262144 8
8 30000 65536 262144 9
9 30000 65536 262144 10
10 30000 65536 262144 11
11 30000 65536 262144 12
12 30000 65536 262144 13
13 30000 65536 262144 14
14 30000 65536 262144 15
15 30000 65536 262144 16
16 30000 65536 262144 17
17 30000 65536 262144 18
18 30000 65536 262144 19
19 30000 65536 262144 20
20 30000 65536 262144 21
21 30000 65536 262144 22
22 30000 65536 262144 23
23 30000 65536 262144 24
24 30000 65536 262144 25
25 30000 65536 262144 26
26 30000 65536 262144 27
27 30000 65536 262144 28
28 30000 65536 262144 29
29 30000 65536 262144 30