29779번 - Colliding Encoding 서브태스크다국어

문제

Alan just had his first cryptography class in school today. He decided to apply what he learned and come up with his own cipher. He will map each English letter from A to Z to a decimal digit 0ドル$ through 9ドル$. He will then try to encode each word to a string consisting of decimal digits by replacing each letter in the word with its mapped digit.

In his excitement, Alan failed to notice that there are 26ドル$ letters in the English alphabet and only 10ドル$ decimal digits. As a result, there might be collisions, that is, pairs of different words whose encoding is the same.

Given a list of $\mathbf{N}$ words that Alan wants to encode and the mapping that he uses, can you find out if there would be any collisions between words on the list?

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains 26ドル$ decimal digits (integers between 0ドル$ and 9ドル,ドル inclusve) $\mathbf{D_A}, \mathbf{D_B}, \dots, \mathbf{D_Z},ドル representing the mapping that Alan uses. A letter $\alpha$ is mapped to digit $\mathbf{D_\alpha}$.

The second line of each test case contains $\mathbf{N},ドル the number of words Alan will encode.

The $i$-th of the last $\mathbf{N}$ lines contains a string $\mathbf{S_i},ドル representing the $i$-th word Alan will encode.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is either YES, if there is at least one pair of different words from the list whose encoding coincides, and NO otherwise.

제한

• 1ドル \le \mathbf{T} \le 100$.
• 0ドル \le \mathbf{D_\alpha} \le 9,ドル for all $\alpha$.
• 1ドル \le $ the length of $ \mathbf{S_i} \le 10,ドル for all $i$.
• Each character of $\mathbf{S_i}$ is an uppercase English letter A through Z, for all $i$.
• $\mathbf{S_i} \ne \mathbf{S_j},ドル for all $i \ne j$.

Test Set 1 (4점)

• 1ドル \le \mathbf{N} \le 100$.

Test Set 2 (10점)

• 1ドル \le \mathbf{N} \le 6 \times 10^4$.

힌트

In Sample Case #1, the mapping for A is 0ドル,ドル for B is 1ドル,ドル for C is 2ドル,ドル for D is 3ドル,ドル and for E is 3ドル$. With this mapping, ABC is encoded as 012ドル,ドル BC is encoded as 12ドル,ドル BCD as 123ドル,ドル and CDE as 233ドル$. Since all of these encodings are distinct, there are no collisions.

In Sample Case #2, the mapping for C is 2ドル,ドル for D is 3ドル,ドル for E is 3ドル,ドル for F is 3ドル,ドル and for G is 3ドル$. With this mapping, CDE is encoded as 233ドル,ドル DEF as 333ドル,ドル and EFG as 333ドル$. Since the encoding for DEF and EFG is the same, there is a collision.