2001 Canadian Computing Competition, Stage 1

Problem S5: Post's Correspondence Problem

Let A and B be two sequences of non-empty strings:
A = (a₁, a₂, ..., a_n), B = (b₁, b₂, ..., b_n).
Let m be a positive integer. Does there exist a sequence of integers
i₁, i₂, ..., i_k such that m > k > 0 and a_i1a_i2...a_ik = b_i1b_i2...b_ik?

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

The first two lines of input will contain m and n respectively, and m x n ≤ 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

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
jkl
mno
pqr

Sample Output 2

No solution.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 10.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can anyone tell me why my program gives a SIGABRT error on the third and fourth test case? I tested the cases on my computer, and it runs fine. 

You're using too much memory.

I believe there's only one possible solution for each test case because my code works without really considering k to be minimal.