Word ladder

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Input

Output

Sample Input

4
cat
cot
scat
sat
7
welcome
to
the
acm
regional
programming
contest
0

Sample Output

3
1

Hint

 

Source

2009 Mid-Atlantic Regional Programming Contest