P2506 [SCOI2008] Poor-quality Encoding

Sichuan NOI Qualifier 2008.

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.

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 a single line containing an integer: the length of the shortest encoding. If there is no solution, output -1.

Constraints: $2 \le n \le 30$. Translated by ChatGPT 5