Canadian Computing Competition: 2001 Stage 1, Senior #5

Let ~A~ and ~B~ be two sequences of non-empty strings:

$$\displaystyle \begin{align*} A &= (a_1, a_2, \dots, a_n) \\ B &= (b_1, b_2, \dots, b_n) \end{align*}$$

Let ~m~ be a positive integer. Does there exist a sequence of integers ~i_1, i_2, \dots, i_k~ such that ~m > k > 0~ and ~a_{i_1} a_{i_2} \dots a_{i_k} = b_{i_1} b_{i_2} \dots b_{i_k}~?

For example, if ~A = (a, abaaa, ab)~ and ~B = (aaa, ab, b)~, then the required sequence of integers is ~(2, 1, 1, 3)~ giving ~abaaaaaab = abaaaaaab~.

Input Specification

The first two lines of input will contain ~m~ and ~n~ respectively, and ~m \times n \le 40~. The next ~2n~ lines contain in order the elements of ~A~ followed by the elements of ~B~. Each string is at most ~20~ characters.

Output Specification

If a solution exists, print ~k~ on a line by itself, followed by the integer sequence in order, one element per line. Otherwise, print a single line containing No solution..

Sample Input 1

7
3
a
abaaa
ab
aaa
ab
b

Sample Output 1

4
2
1
1
3

Sample Input 2

10
3
abc
def
ghi
bcd
efg
hia

Sample Output 2

No solution.