Post's Correspondence Problem

You are given two sequences of non-empty strings, both of length $n$:

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

You are also given a positive integer $m$. Decide whether there exists a sequence of indices $i_1, i_2, \dots, i_k$ (each $i_j$ between $1$ and $n$, repetitions allowed) with $0 < k < m$ such that concatenating the chosen strings from $A$ yields the same string as concatenating the same-indexed strings from $B$:

$$a_{i_1} a_{i_2} \cdots a_{i_k} = b_{i_1} b_{i_2} \cdots b_{i_k}$$

For instance, with $A = (a,\ abaaa,\ ab)$ and $B = (aaa,\ ab,\ b)$, the indices $(2, 1, 1, 3)$ work because both sides spell $abaaaaaab$.

The first line contains the integer $m$, and the second line contains the integer $n$. The next $2n$ lines contain, in order, the strings $a_1, \dots, a_n$ followed by $b_1, \dots, b_n$, one per line. Every string is non-empty and at most $20$ characters long, and $m \times n \le 40$.

A matching sequence need not be unique, so output the canonical one. Among all valid sequences, choose those of the smallest length $k$; if several sequences tie for that minimum length, choose the lexicographically smallest one (compare the index lists element by element).

If such a sequence exists, print $k$ on its own line, followed by the indices $i_1, i_2, \dots, i_k$ in order, one per line. Otherwise, print a single line containing No solution.