Rhyme

Time limit1sMemory limit256 MB

Summary

Given N distinct words, find the longest sequence using each word at most once where consecutive words rhyme: their longest common suffix has length at least the longer word's length minus one.

Level: Hard8 of 10
Topics: String, Trie, Graph, DFS
Solved: No attempts yet

Problem

Adrian likes rhymes. He decides that two words rhyme if and only if the length of their longest common suffix equals the length of the longer word, or falls exactly 1 short of it. In other words, words $A$ and $B$ rhyme if and only if

$\mathrm{LCS}(A, B) \ge \max(|A|, |B|) - 1$

Here $\mathrm{LCS}(A, B)$ is the length of the longest common suffix of $A$ and $B$ , and $|A|$ is the length of $A$ .

One day, while reading a collection of short stories, Adrian decided to lay out the longest possible sequence of words in which every two consecutive words rhyme. The words come from the given list, and no word may be used twice.

Adrian got tired of the task and went back to reading. Given $N$ words, write a program that computes the maximum length of such a sequence.

Input

The first line contains the number of words $N$ ( $1 \le N \le 500\,000$ ).

Each of the next $N$ lines contains one word. Every word consists of lowercase English letters, and all words are distinct. The sum of the word lengths is at most $3\,000\,000$ .

Output

Print the length of the longest sequence.

Examples3

Example 1
Input
```
4
honi
toni
oni
ovi
```
Expected output
```
3
```
Example 2
Input
```
5
ask
psk
krafna
sk
k
```
Expected output
```
4
```
Example 3
Input
```
5
pas
kompas
stas
s
nemarime
```
Expected output
```
1
```