题目描述

给定一个包含n个单词的字典，从中选择若干个单词，按字典序进行单词接龙，使得接龙的长度最大。

新单词接龙的规则：

1. 单词变换：单词wi 添加一个字母，删除一个字母，或修改一个字母可以得到单词wi+1。

2. 字典序接龙：w1, w2, …, wn, 满足字典序。

输入格式

第一行一个整数n（1≤n≤25,000），表示字典中单词的总数。接下来n行，按字典序输入n个单词，每行一个字符串，表示单词，单词仅由小写字母组成，长度为1..16。

输出格式

输出一行一个整数，表示能获得的单词接龙的最大长度。

9
cat
dig
dog
fig
fin
fine
fog
log
wine

5

提示

样例说明:

长度为5的单词接龙为：digàfigàfinàfineàwine。