## 1140 - Ambiguous Codes

Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 11

Solved: 2

Description
An extensive area of research in computer science is the ﬁeld of communications. With computer
networks being part of everyday life of many people, the development of ways for making
networks faster, more reliable and secure is constantly needed. This practical need motivates
an extensive research activity in the theory behind communications.
The very ﬁrst thing needed to establish any kind of communication is a common code. A code
is a way of changing the form of a piece of information into some other form, in general to make
it possible to convey that piece of information from one place to another. Flag codes used by
boats and the Morse code used in telegraphy are examples of codes for translating letters into
diﬀerent forms to enable communication over diﬀerent media.
More formally, a code is a set of strings composed of symbols from one alphabet. Each string
deﬁned in the code is called a code word. A message is then composed concatenating a set
of code words to convey the information needed. For example, in Morse code the alphabet is
composed of the symbols hyphen and dot; letter “S” is represented by the code word “...”,
letter “O” is represented by the code word “---”, and therefore the distress message “SOS” in
Morse code is “...---...”.
Codes for communication can have many desirable and undesirable properties such as ambiguity,
entropy, redundancy, and many more. In this problem we will focus on ambiguity as a key
property.
A code is ambiguous when there exists a message using that code that can be partitioned into
diﬀerent sequences of code words. In other words, in an ambiguous code a message may have
more than one meaning. For example, consider the binary alphabet, composed of symbols
{0,1}. For the code composed of the words {10, 01, 101} the message 10101 can be understood
as 10-101 or 101-01 and therefore the code is ambiguous. On the other hand, for the code
composed of the words {01, 10, 011} no ambiguous message exists and therefore the code is
unambiguous.
As a part of the computer science community, you are required to develop a tester that checks
if codes are ambiguous. In case a code is indeed ambiguous, you are also required to report the
length (i.e. the number of symbols) of the shortest ambiguous message for that code.
Input
Each test case will consist on several lines. In all test cases the alphabet will be the set of
hexadecimal digits (decimal digits plus the uppercase letters “A” to “F”). The ﬁrst line of a test
case will contain an integer N (1 ≤ N ≤ 100), the number of code words in the code. Each
of the next N lines describes a code word and contains a diﬀerent and non-empty string of at
Input is terminated by N = 0.
The input must be read from standard input.
Output
For each test case, output a single line with the length of the shortest ambiguous message for
the provided code or -1 if the code is unambiguous.
The output must be written to standard output.
sample input
```3
10
01
101
3
AB
BA
ABB
0```
sample output
```5
-1```
hint
source
ACM ICPC2007 – South American Regionals
© 2015 HUST ACMICPC TEAM. All Right Reserved.