编程题：动态规划

小艾德里安喜欢押韵。他认为，当且仅当两个单词的最长共同后缀与两个单词的长相同，或比长单词短$$1$$时，两个单词才押韵。换句话说，当且仅当它成立时，$$A$$和$$B$$押韵。$$LCS(A, B) ≥ max(|A|, |B|) -1$$。
有一天，他在读一本短篇小说集时，决定把单词排列得尽可能长，使每两个连续的单词押韵。序列中的每个单词只能出现一次。
$$Adrian$$已经厌倦了这个任务，所以他决定回去看书，让你来解决这个任务。

### 输入格式:

输入第一行为整数$$N(1≤N≤500000)$$。下面N行每一行包含一个由英文字母小写组成的单词。所有单词都是相互不同的，它们的总长度最多为$$3 000 000$$。

### 输出格式:

你必须输出最长序列的长度。

### 得分：
在占$$30$$%的测试用例中，它将保持$$N≤18$$。


### 输入样例1:

in
4
honi
toni
oni
ovi


### 输出样例1:

out
3


### 输入样例2:

in
5
ask
psk
krafna
sk
k


### 输出样例2:

out
4



### 输入样例3:

in
5
pas
kompas
stas
s
nemarime


### 输出样例3:

out
1








答案：若无答案欢迎评论