A1570.[COCI-2016_2017-contest4]#6 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|) −

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 00
0.

You must output the length of the longest sequence.

In test cases worth 30% of points, it will hold N ≤ 18.

Clarification of the second test case:
The only possible sequence is ask-psk-sk-k.
Clarification of the third test case:
No two words rhyme.