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 str_1..∞ 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 str_i..j is a banned word in S (1 <= i <= j < ∞).
3. There does not exist such (i, j) that for any k >= i, str_k = 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

22 2aabb1 2aa

Sample Output

NoYes

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 using namespace std;  6 const int CHAR = 26;  7 const int TOT = 100005;  8 int next[TOT][CHAR], fail[TOT];  9 bool virus[TOT]; 10 int L, root; 11 int m; 12 int newNode() { 13     for (int i=0; i
          

Q; 31 for (int i=0; i

s; 58 struct node 59 { 60 int v, next; 61 }edge[maxm]; 62 void add_edge(int u, int v) 63 { 64 edge[e].v=v; 65 edge[e].next=head[u]; 66 head[u]=e++; 67 } 68 void init() 69 { 70 memset(head, -1, sizeof(head)); 71 memset(id, 0, sizeof(id)); 72 memset(vis, 0, sizeof(vis)); 73 memset(dfn, 0, sizeof(dfn)); 74 while (!s.empty()) s.pop(); 75 e=Time=sz=0; 76 L=0; 77 root=newNode(); 78 } 79 int Min(int a, int b) 80 { 81 if (a<=b) return a; 82 return b; 83 } 84 void tarjan(int u) 85 { 86 int v; 87 dfn[u]=low[u]=++Time; 88 s.push(u); 89 vis[u]=1; 90 for (int i=head[u]; i!=-1; i=edge[i].next) { 91 v=edge[i].v; 92 if (!dfn[v]) { 93 tarjan(v); 94 low[u]=Min(low[u], low[v]); 95 } 96 else if (vis[v]) low[u]=Min(low[u], dfn[v]); 97 } 98 if (dfn[u]==low[u]) { 99 sz++;100 do {101 v=s.top();102 s.pop();103 id[v]=sz;104 vis[v]=0;105 }while(v!=u);106 }107 }108 bool judge()109 {110 int cnt;111 for (int i=0; i

=2) return 1;116 }117 }118 return 0;119 }120 char str[1005];121 int main()122 {123 int cas, n;124 scanf("%d", &cas);125 while(cas--) {126 scanf("%d %d", &n, &m);127 init();128 while (n--) {129 scanf(" %s", str);130 insert(str);131 }132 build();133 for (int i=0; i