14213번 - Rima 다국어

Little Adrian is a fan of rhyme. He believes that two words rhyme if and only if their longest common suffix is as long as the longer of the two words, or shorter than the longer word by 1. In other words, A and B rhyme if and only if it holds . LCS(A, B) ≥ max(|A|, |B|) - 1

One day, while reading a collection of short stories, he decided to compose the longest possible sequence of words such that each two consecutive words rhyme. Each word from the sequence can appear only once.

Adrian has grown tired of this task, so he decided to go back to reading, and is asking you to solve this task instead of him. 

The first line of input contains the integer N (1 ≤ N ≤ 500 000).

Each of the following N lines contains one word consisting of lowercase letters of the English alphabet. All words are mutually distinct, and their total length is at most 3 000 000. 

You must output the length of the longest sequence.