Transform a begin word into an end word by changing one letter at a time; every intermediate word must be in the word list (the end word must be in it too). Return the number of words in the shortest transformation sequence, counting both ends.
Input: line 1 — begin end; line 2 — space-separated word list.
Output: the length of the shortest sequence, or 0 if none exists.
Your program reads from stdin and prints to stdout.
Example 1
Input: hit cog hot dot dog lot log cog
Output: 5
Hints
Transform a begin word into an end word by changing one letter at a time; every intermediate word must be in the word list (the end word must be in it too). Return the number of words in the shortest transformation sequence, counting both ends.
Input: line 1 — begin end; line 2 — space-separated word list.
Output: the length of the shortest sequence, or 0 if none exists.
Your program reads from stdin and prints to stdout.
Example 1
Input: hit cog hot dot dog lot log cog
Output: 5
Hints