Impressed, the freshmen challenge Rina with a classic word puzzle from their algorithms class: transform one word into another one letter at a time, using only real dictionary words at every step, in as few steps as possible. Given a start word, an end word, and a dictionary of N words (all same length), find the length of the shortest transformation sequence from start to end, changing exactly one letter at a time, where every intermediate word must exist in the dictionary. Print -1 if impossible.
Input
Line1: start end. Line2: N. Next N lines: dictionary words.
Output
Length of shortest transformation sequence (number of words including start and end), or -1.
Constraints
1 ≤ N ≤ 5000, all words equal length ≤ 10
Sample Input
hit cog 6 hot dot dog lot log cog
Sample Output
5
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.