6935번 - Post's Correspondence Problem 다국어

문제

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$.

입력

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

출력

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..

제한

힌트