Bad Codes

시간 제한1초메모리 제한512 MB

요약

길이가 M 이하인 N개의 이진 부호어가 주어질 때, 서로 다른 두 부호어 열로 해석되는 가장 짧은 이진 문자열의 길이를 구하고, 그런 문자열이 없으면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 문자열, BFS, 그래프, 트라이
정답자: 아직 제출이 없습니다

문제

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:

A → 101 B → 10 C → 1 D → 100

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

Your job is 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.

입력

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

출력

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.

예제2

예제 1
입력
```
4 3
101
10
1
100
```
예상 출력
```
3
```
예제 2
입력
```
4 4
1011
1000
1111
1001
```
예상 출력
```
-1
```