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.