描述

一次编辑步骤是指从一个单词$x$转换为另一个单词$y$，其中$x$和$y$都在字典中，并且$x$可以通过添加、删除或更改一个字母转换为$y$。例如，从$“dig”$到$“dog”$，或者从$“dog”$到$“do”$的转换都属于一次编辑步骤。编辑步骤阶梯是一个按字典序排列的单词序列$w_1, w_2, \ldots, w_n$，对于所有从$1$到$n - 1$的$i$，从$w_i$到$w_{i + 1}$的转换都是一次编辑步骤。

输入

对于给定的字典，你需要计算最长编辑步骤阶梯的长度。输入的内容是字典，即一组按字典序排列的小写单词，每行一个单词。每个单词的长度不超过$16$个字母，且字典中单词数量不超过$25000$个。

输出

输出为一个整数，表示最长编辑步骤阶梯中的单词数量。

输入数据1

cat
dig
dog
fig
fin
fine
fog
log
wine

输出数据1

5

来源

滑铁卢当地（竞赛）$2000$年$9$月$23$日