포스트 대응 문제

같은 길이 $n$을 가지는, 비어 있지 않은 문자열 두 수열이 주어진다.

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

또한 양의 정수 $m$이 주어진다. 각 $i_j$가 $1$ 이상 $n$ 이하이고(중복 허용) $0 < k < m$을 만족하는 인덱스 수열 $i_1, i_2, \dots, i_k$가 존재하여, $A$에서 고른 문자열들을 순서대로 이어 붙인 결과와 $B$에서 같은 인덱스로 고른 문자열들을 이어 붙인 결과가 같아지는지 판정하라.

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

예를 들어 $A = (a,\ abaaa,\ ab)$, $B = (aaa,\ ab,\ b)$이면 인덱스 $(2, 1, 1, 3)$이 조건을 만족한다. 양쪽 모두 $abaaaaaab$가 되기 때문이다.

첫째 줄에 정수 $m$, 둘째 줄에 정수 $n$이 주어진다. 이어지는 $2n$개의 줄에는 문자열 $a_1, \dots, a_n$과 $b_1, \dots, b_n$이 순서대로 한 줄에 하나씩 주어진다. 모든 문자열은 비어 있지 않으며 길이는 최대 $20$이고, $m \times n \le 40$이다.

조건을 만족하는 수열은 유일하지 않을 수 있으므로, 정해진 하나만 출력한다. 모든 유효한 수열 중 길이 $k$가 가장 작은 것을 고르고, 그러한 수열이 여러 개면 사전순으로 가장 앞서는 것(인덱스 목록을 앞에서부터 원소 단위로 비교)을 고른다.

그런 수열이 존재하면 첫 줄에 $k$를, 이어서 인덱스 $i_1, i_2, \dots, i_k$를 순서대로 한 줄에 하나씩 출력한다. 존재하지 않으면 No solution. 한 줄만 출력한다.