Valid Prefixes

Special Judge Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      A context free grammar consists of Σ — the set of characters, N — the set of variables, S ∈ N — the starting variable, and a finite set — the set of productions. The production is usually denoted asIn this problem and variables are denoted by capital letters of the English alphabet. An empty word is denoted as .Let β and γ be words over  Ifwe say that β tranforms to γ and write  In other words, if  it is allowed to take β and replace any occurance of A with the word α ,We will sayif γ can be obtained from β with zero or more transformations. For example, let In this case  since

      The number of characters  in a word α is called the length of this word and is denoted as |α|

Let k be an integer number. We say that a word is a valid k-pre x if one of the following is true:

             

      Given a context free grammar and a number k find all valid k-prefixes.

Input

      The first line of the input file contains two integer numbers: n — the number of productions in the given grammar, and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 6). The following n lines contain one production each. The length of the right part of each production doesn’t exceed 10. The starting variable of the grammar is S.

Output

      The first line of the output file must contain a number m — the number of valid k-prefixes. The following m lines must contain one prefix each. Use “eps” to denote an empty word.

Sample Input

2 3
S->0S1S
S->
1 3
S->SS
1 3
A->0

Sample Output

5
eps
000
001
01
010
0
0

Source

Andrew Stankevich Contest 22

Manager

Information
Solved Number1
Submit Number1
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel