시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Jisung is the student representative of the Department of Computer Engineering in ACM University. A few days later, the annual festival will be held for the students in the department. He is preparing some events for the festival. Since Jisung likes to make and solve puzzles, he decides to devise some interesting puzzle for the festival.
The followings are the rules for the puzzle made by Jisung:
For example, suppose the given number n=2, i.e., the players can use the two characters A and B. Assume that the forbidden strings are {AAA, AB, BA, BB}. In this case, the longest string that does not include any of the four forbidden strings as substrings is AA. But if the given forbidden strings are {AAA, BBB, ABAB, BBAA}, we cannot make such a longest string since arbitrarily long concatenations of ABA, i.e., ABAABAABA… do not include any forbidden string.
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers n (1 ≤ n ≤ 26) and s (1 ≤ s ≤ 1,000) which represent the number of characters and the number of forbidden strings, respectively. From the second line to (s+1)-st line of the test case, the forbidden strings are given one by one. The length of a forbidden string does not exceed 50.
Your program is to write to standard output. Print exactly one line for each test case. Print the longest string that does not include any forbidden string as a substring if it exists, otherwise, just print ‘No’ as output. When there exists more than one such longest string with the same length, print the lexicographically largest string among them.
The following shows sample input and output for three test cases.
3 2 4 AAA AB BA BB 2 4 AAA BBB ABAB BBAA 3 7 AA ABA BAC BB BC CA CC
AA No ACBAB
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2007 H번