Description

An encoding scheme maps each character to a 01 string. For example, {1, 1010, 01, 10101} is an encoding scheme that maps four characters (assume they are a, b, c, d) to the strings 1, 1010, 01, 10101 respectively. The encoding of a string is the concatenation of the encodings of its characters. For instance, under the above scheme, the encoding of cac is 01101, and the encoding of dcb is 10101011010.

On further analysis, the above scheme is quite poor-quality, because the encodings of ba, acc, and d are all 10101. For a given encoding scheme, your task is to find three distinct strings whose encodings are identical. In other words, find a 01 code string that has at least three decoding ways. If there are multiple solutions, this code string should be as short as possible.

Input Format

The first line contains an integer $n$, the number of symbols. Each of the following $n$ lines contains a 01 string (possibly empty) of length at most 50, which is the encoding of a symbol.

Output Format

Output a single line containing an integer: the length of the shortest encoding. If there is no solution, output -1.

4
1
1010
01
10101

5

2
0
1

-1

7
00011011
000110
11
0001
1011
00
011011

8

Hint

Constraints: $2 \le n \le 30$.

Translated by ChatGPT 5