Shom Code

Time limit2sMemory limit128 MB

Summary

Given binary codes assigned to up to 26 letters, find the minimum length of a binary string decodable as three or more distinct letter sequences, or -1 if none exists.

Level: Hard9 of 10
Topics: Trie, BFS, String matching, Graph
Solved: No attempts yet

Problem

Each alphabet letter is assigned a code made only of 0s and 1s. A code may also have length 0. To encode a string, replace its letters from left to right by their assigned codes and concatenate the results.

For instance, suppose the alphabet set is {a, b, c, d} and the assignment is f(a)=1, f(b)=1010, f(c)=01, and f(d)=10101. Then the string cac is encoded as 01101 by concatenating 01, 1, and 01.

If one binary code can be interpreted as two different strings, it is ambiguous. If it can be interpreted as three or more different strings, it is really ambiguous. Under the assignment above, 10101 is really ambiguous because it can be interpreted as ba, acc, and d.

Given the list of assigned codes, find the minimum length of a binary code that can be interpreted as three or more different strings.

Input

The first line contains the number of codes N. N is an integer between 2 and 26, inclusive.

Each of the next N lines contains the code assigned to one alphabet letter. Each code consists only of 0s and 1s and has length at most 50. A code of length 0 is given as -1. Different letters may have identical codes.

Output

Print the minimum length of a binary code that can be interpreted as three or more different strings. If no such code exists, print -1.

Examples8

Example 1
Input
```
4
1
1010
01
10101
```
Expected output
```
5
```
Example 2
Input
```
2
0
1
```
Expected output
```
-1
```
Example 3
Input
```
4
0
11
11
11
```
Expected output
```
2
```
Example 4
Input
```
5
0000
001
01001
01010
01011
```
Expected output
```
-1
```
Example 5
Input
```
3
1
10
00
```
Expected output
```
-1
```
Example 6
Input
```
3
-1
01101001001
111101011
```
Expected output
```
0
```

Example 7

Input

Expected output

Example 8
Input
```
4
0
1
01
11
```
Expected output
```
3
```