Word Ladder Length

Word Ladder Length

Given a start word, an end word, and a dictionary of words (all the same length as start/end, lowercase letters only), find the length (number of ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌‌​‌‌​​​‌‌​‌‌​​‌​​​‌‌​​‌‌​​​‌‌​‌​‌​‌‌​​‌​​​‌‌​​‌​‌​‌‌​​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌​‌‌​words, including start and end) of the shortest transformation sequence from start to end, where each step changes exactly one letter and every intermediate word (including end, but not necessarily start) must appear in the dictionary. If no such sequence exists (including if end is not in ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌‌​‌‌​​​‌‌​‌‌​​‌​​​‌‌​​‌‌​​​‌‌​‌​‌​‌‌​​‌​​​‌‌​​‌​‌​‌‌​​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌​‌‌​the dictionary), output 0.

Input

Line 1: two words start end Line 2: integer n, the dictionary size (0 ≤ n ≤ 2000) Next n lines: one dictionary word each

Output

A single integer: the shortest transformation length, or 0 if impossible.

Example

Input:

hit cog
6
hot
dot
​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌‌​‌‌​​​‌‌​‌‌​​‌​​​‌‌​​‌‌​​​‌‌​‌​‌​‌‌​​‌​​​‌‌​​‌​‌​‌‌​​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌​‌‌​dog
lot
log
cog

Output:

5

Constraints

• All words have equal length, at most 12, lowercase letters only.
• 0 ≤ n ≤ 2000 ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌​‌‌‌​‌‌​​​‌‌​‌‌​​‌​​​‌‌​​‌‌​​​‌‌​‌​‌​‌‌​​‌​​​‌‌​​‌​‌​‌‌​​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​‌​​‌‌​‌‌​

cat cot
3
cot
dot
dog

2

hit cog
6
hot
dot
dog
lot
log
cog

5