Edit Step Ladders

An *edit step* is a transformation from one word
$x$ to another word
$y$ such that $x$ and $y$ are words in the dictionary, and
$x$ can be transformed to
$y$ by adding, deleting,
or changing one letter. So the transformation from “`dig`” to “`dog`” or from
“`dog`” to “`do`” are both edit steps. An *edit step
ladder* is a lexicographically ordered sequence of words
$w_1, w_2, \ldots w_ n$
such that the transformation from $w_ i$ to $w_{i+1}$ is an edit step for all
$i$ from $1$ to $n-1$.

For a given dictionary, you are to compute the length of the longest edit step ladder.

The input to your program consists of the dictionary – a set of lower case words in lexicographic order – one per line. No word exceeds $16$ letters and there are no more than $50\, 000$ words in the dictionary.

The output consists of a single integer, the number of words in the longest edit step ladder.

Sample Input 1 | Sample Output 1 |
---|---|

cat dig dog fig fin fine fog log wine |
5 |