### 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_{1}, a_{2}, ..., a_{n}), B = (b_{1}, b_{2}, ..., b_{n}).

Let *m* be a positive integer. Does there exist a sequence of integers

i_{1}, i_{2}, ..., i_{k} such that m > k > 0 and a_{i1}a_{i2}...a_{ik} =
b_{i1}b_{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 2*n* 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

**Problem Types:**[Show]

**Languages Allowed:**

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

## Comments (Search)

pyrexshortson Feb 07, 2015 - 5:30:46 pm UTC SIGABRT on 3 and 4?jargonon Feb 09, 2015 - 10:39:33 pm UTC Re: SIGABRT on 3 and 4?Bobon Feb 24, 2009 - 7:25:12 pm UTC I'm assuming k has to be minimal?Saravannanon Feb 24, 2009 - 10:48:47 pm UTC Re: I'm assuming k has to be minimal?