Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 12 Contest LoginRegister Exam
2017 ACM 集训队预选排名~      报名入口
Problem 1082. -- Edit Step Ladders

Edit Step Ladders

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 4  Solved: 0
[Submit][Status][Discuss]

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 length of the longest edit step ladder.

Input

The input to your program consists of the dictionary: a set of lowercase words in lexicographic order at one word per line. No word exceeds 16 letters and there are at most 25,000 words in the dictionary.

Output

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

Sample Input

cat
dig
dog
fig
fin
fine
fog
log
wine

Sample Output

5

HINT

Source

Waterloo local 2000.09.23

[Submit][Status][Discuss]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin