Indian National Olympiad in Informatics

Related:

Online Programming Contest, 24-25 December 2005

IARCS home > OLYMPIAD

Advanced Division

Problem 1: Word Hopping, (K Narayan Kumar, CMI)

In this problem we are concerned with words constructed using the lowercase letters of the English alphabet - that is, a,b,c,...,z. These words need not necessarily be meaningful: any sequence of letters forms a word. For example, abbca is a word.

We say that we can "hop" from the word w₁ to the word w₂ if they are "sufficiently close". We define w₂ to be sufficiently close to w₁ if one of the following holds:

w₂ is obtained from w₁ by deleting one letter.
w₂ is obtained from w₁ by replacing one of the letters in w₁ by some letter that appears to its right in w₁ and which is also to its right in alphabetical order.

For example, we can hop from abbca to abca by deleting the second (or third letter). We can hop from aabca to abbca by replacing the a in the second position by the letter b that appears to the right of the a in aabca and which is also to its right in alphabetical order. On the other hand we cannot hop from abbca to aabca since we would need to replace the b in the second position by a, but a is to the left of b in alphabetical order.

You will be given a collection of words W. Your task is to find the length of the longest sequence w₁, w₂, ... of distinct words from W such that we may hop from w₁ to w₂, w₂ to w₃ and so on. We call this the hopping number for this set.

For example, if

W = {abacd, bcdada, dd, abcd,bcdd, adcd, addd, aa, ccd, add, ad}

then, the hopping number is 7 corresponding to the sequence

abacd, abcd, adcd, addd, add, ad, dd

Input format

The first line of the input contains one integer N indicating the number of words in the input. This is followed by N lines of input, lines 2, 3,..., N+1, each containing one word over the letters {a,b,..., z}.

Output format

The output should be a single integer, indicating the hopping number of the given set of words.

Test Data:

You may assume N ≤ 100. You may assume that each word has at most 10 letters.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

11
abacd
bcdada
dd
abcd
bcdd
adcd
addd
aa
ccd
add
ad

Sample Output