편집 단계 사다리

편집 단계(edit step)란 한 단어 $x$를 다른 단어 $y$로 바꾸는 변환을 말한다. 단, $x$와 $y$는 모두 사전에 들어 있는 단어여야 하며, $x$에 글자 하나를 추가하거나, 글자 하나를 삭제하거나, 글자 하나를 다른 글자로 바꾸어 $y$를 만들 수 있어야 한다. 예를 들어 dig에서 dog으로, 또는 dog에서 do로 바꾸는 것은 모두 편집 단계이다.

편집 단계 사다리(edit step ladder)는 사전순으로 정렬된 단어들의 수열 $w_1, w_2, \ldots, w_n$으로, $1 \le i \le n-1$인 모든 $i$에 대해 $w_i$에서 $w_{i+1}$로의 변환이 편집 단계인 것을 말한다.

주어진 사전에 대해 가장 긴 편집 단계 사다리의 길이를 구하여라.

입력은 사전이다. 사전순으로 정렬된 소문자 단어들의 집합이 한 줄에 하나씩 주어진다. 각 단어의 길이는 16글자를 넘지 않으며, 사전에 들어 있는 단어는 최대 25000개이다.

가장 긴 편집 단계 사다리에 포함된 단어의 개수를 정수 하나로 출력한다.