Description

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. The transformations from dig to dog and from dog to do are both edit steps. An edit step ladder is a lexicographically ordered sequence of words w1, w2, ..., wn such that the transformation from wi to wi+1 is an edit step for all i from 1 to n - 1.

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

Input

The input consists of a dictionary: a set of lowercase words in lexicographic order at on word per line. No word exceeds 16 letters and there are at most 25,000 words in the dictionary. Here is an sample input:

cat
dig
dog
fig
fin
fine
fog
log
wine

Output

Output a single integer denoting the number of words in the longest edit step ladder. For example, output:

5

Approach

Approach the problem as a searching a DAG. The words are the nodes and the edges are where words form an edit step. Once this graph is formed, you can simply perform a depth-first search from all the nodes to find out the longest sequence.

Input/Output

• Final Input: problem021.input
• Final Output: problem021.output

Source Code

• Peter Bui's source code: pbui.cc
• Dominic Golab's source code: dgolab.cpp