Heavy Souls

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem type

After his latest misadventure, the Tushan Foxen realized the peculiarity of the Yuechu family's reincarnation. After multiple reincarnations, Bai Yuechu has retained the souls of his previous ancestors. As such, it may occasionally be difficult to figure out which soul is in control of his body.

However, we know that each ancestor comes from a different era and consequently only know certain characters from that era. Since the problem setters are not evil, we will give you ASCII characters in place of the traditional Chinese characters that were originally used.

Each soul has an alphabet, consisting of lowercase English letters from a to t. Given a list of alphabets, help determine the minimum length of a string that could be used to determine which soul is in control. Specifically, give the length of a string of minimum length such that only one soul can speak that string using their alphabet. If there is no such string, output -1.

Input Format

Line 1: An integer N (1 \le N \le 50\,000), the number of souls.

Next N lines: A sequence of lowercase English characters between a and t on each line, each with at most 20 characters.

Sample Input


Sample Output



One such string is aqt.


There are no comments at the moment.