新单词接龙问题

题目描述

给定一个包含 $n$ 个单词的字典,从中选择若干个单词,按字典序进行单词接龙,使得接龙的长度最大。 新单词接龙的规则: 1. 单词变换:单词 $w_i$ 添加一个字母,删除一个字母,或修改一个字母可以得到单词 $w_i+1$; 2. 字典序接龙:$w_1,w_2,\cdots,w_n$,满足字典序。

输入输出格式

输入格式


第一行一个整数 $n$($1 \le n \le 25,000$),表示字典中单词的总数。接下来 $n$ 行,按字典序输入 $n$ 个单词,每行一个字符串,表示单词,单词仅由小写字母组成,长度在 $1$ 至 $16$ 以内。

输出格式


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

输入输出样例

输入样例 #1

9
cat
dig
dog
fig
fin
fine
fog
log
wine

输出样例 #1

5

说明

### 样例解释 长度为 $5$ 的单词接龙为:$\texttt{dig\underline afigafin\underline afine\underline awine}$。