Canadian Computing Olympiad: 2019 Day 2, Problem 3

Your friend has constructed a code that they want to use to send secret messages to you. The messages will only be composed of ~N~ different symbols and each symbol will correspond to one binary sequence with at most ~M~ bits.

However, you are not sure the code is going to work: there is a chance that a binary sequence can correspond to two (or more) different messages.

For example, if the code was:

$$\displaystyle \begin{align*} A &\to 101 \\ B &\to 10 \\ C &\to 1 \\ D &\to 100 \end{align*}$$

then the binary sequence ~101~ could correspond to either ~A~ or ~BC~.

Your job is to determine the length of the shortest binary sequence that corresponds to two different messages, or determine that there are no binary sequences which correspond to two different messages.

Input Specification

The first line of input will contain two space-separated integers ~N~ and ~M~ ~(1 \le N, M \le 50)~. The next ~N~ lines of input each will have at least one and at most ~M~ characters from the set ~\{0, 1\}~.

For 4 of the 25 marks available, ~N = 4~ and ~M \le 6~.

For an additional 7 of the 25 marks available, each of the binary sequences will contain exactly one ~1~ bit. For example, the sequences ~00100~ or ~1000~ would be valid in this case.

Output Specification

Output will be one line long.

If there is a binary sequence that corresponds to two (or more) messages, print the length of the shortest such binary sequence; otherwise, output one line containing -1.

Sample Input 1

4 3
101
10
1
100

Output for Sample Input 1

3

Explanation of Output for Sample Input 1

This is the sample in the problem description.

Sample Input 2

4 4
1011
1000
1111
1001

Output for Sample Input 2

-1

Explanation of Output for Sample Input 2

There is no binary sequence that corresponds to more than one message. Notice that since each code is 4 bits, and none are the same, every encoding of ~4k~ bits can be uniquely decoded into ~k~ characters.