P7537 [COCI 2016/2017 #4] Rima

Define the length of the longest common suffix of strings $A, B$ as $\text{LCS}(A,B)$. When $\text{LCS}(A,B) \ge \max(|A|,|B|)-1$, we say that the two strings $A, B$ rhyme. Given $N$ strings, you need to form a longest possible sequence of strings (the sequence length is the number of strings in it) such that every pair of adjacent strings in the sequence rhymes.

The first line contains an integer $N$. The next $N$ lines each contain one string. It is guaranteed that all strings are distinct, consist of lowercase letters, and the total length does not exceed $3 \times 10^6$.

Output the maximum possible length of the string sequence.

**[Explanation of Sample 2]** The string sequence $\texttt{ask-psk-sk-k}$ has the maximum length, which is $4$. **[Explanation of Sample 3]** No two strings rhyme, so any single string can form a sequence by itself. The answer is $1$. **[Constraints]** For $30\%$ of the testdata, $N \le 18$. For $100\%$ of the testdata, $1 \le N \le 5 \times 10^5$. **[Hints and Notes]** **This problem is translated from [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T5 Rima_.** **The score of this problem follows the original COCI setting, with a full score of $140$.** Translated by ChatGPT 5