Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3784
String of Infinity

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given a set of banned words S, please find out whether it is possible to construct a string str1..∞ with infinite length that fulfills the following constrains:

  1. It consists of only the first M types of lowercase letters in the alphabet. For example M = 3, only 'a', 'b' and 'c' are allowed to appear in the string.
  2. There does not exist such (i, j) that stri..j is a banned word in S (1 <= i <= j < ∞).
  3. There does not exist such (i, j) that for any k >= i, strk = str(j + k) (1 <= i, j < ∞).

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N (1 <= N <= 100) and M (1 <= M <= 26). The following N lines, each line contains contains a non-empty string indicating a banned word in S. The length of each word will not exceed 1000 and the word only consists of lowercase letters.

Output

For each test case, output "Yes" if it is possible to construct such a string, otherwise "No".

Sample Input

2
2 2
aa
bb
1 2
aa

Sample Output

No
Yes

Author: CHEN, Weijie
Source: The 11th Zhejiang Provincial Collegiate Programming Contest
Submit    Status