Edit Step Ladders

Time limit1sMemory limit128 MB

Summary

Given a lexicographically sorted dictionary, find the longest sequence of words where each consecutive pair differs by one insertion, deletion, or substitution, and the sequence follows dictionary order.

Level: Medium7 of 10
Topics: Dynamic programming, String, Hash map, Sorting
Solved: No attempts yet

Problem

An edit step is a transformation from one word $x$ into another word $y$ such that $x$ and $y$ are both words in the dictionary, and $y$ can be obtained from $x$ by adding one letter, deleting one letter, or changing one letter. For example, transforming dig into dog, or dog into 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 every $i$ with $1 \le i \le n-1$ .

Given a dictionary, compute the length of the longest edit step ladder.

Input

The input is a dictionary: a set of lower-case words in lexicographic order, one per line. No word is longer than 16 letters, and the dictionary contains at most 25000 words.

Output

Output a single integer: the number of words in the longest edit step ladder.

Examples1

Example 1

Input

cat
dig
dog
fig
fin
fine
fog
log
wine

Expected output