Limits 2s, 512 MB

Many years have passed after Simba's death. The jungle has a new lion cub born just a few hours ago. Everyone came to see their future king. What's his name? Well, that is the problem. They want to give him a name, that was in each of their last N king's name as a unique substring.

The substring should be unique because repeating substrings are not prestigious enough to be the name of a king! And it iscommon between N kings' names, because that's how the jungle pay their tribute to kings, those who have gone in the history and those yet to come. Also, they want their current king's name to be as long as possible. Otherwise they will fall short of names in the future. Can you help them?

You are given N strings consisting of only lowercase English letters. Find the length of the largest common unique substring from them.

A substring is unique if it occurs only once in a string. A common unique substring is a kind of substring which occurs exactly once in each string.

Input

The first line of the input contains one integer N.
The next N lines contain N strings.

Constraints:

2 <= N <=10

2 <= length of each string <= 105

Output

Print the length of the substring as described in the problem statement.

Sample

InputOutput
2
aaaadbbdaaaa
aaaaaaarbbraaaaaaaaa
2

Submit

Login to submit.

Statistics

69% Solution Ratio
mahdi.hasnatEarliest, Nov '19
Kuddus.6068Fastest, 0.1s
samiulsamiLightest, 21 MB
likhon5Shortest, 1903B
Toph uses cookies. By continuing you agree to our Cookie Policy.