Problem Description

Find the shortest transformation sequence from a start word to an end word, changing only one letter at a time. Each intermediate word must be in the given dictionary. Return the length of the shortest path, or 0 if impossible.

Input Format

First line: start word. Second line: end word. Third line: n (dictionary size). Next n lines: dictionary words.

Output Format

Length of shortest transformation path, or 0 if impossible.

Constraints

• 1 ≤ word length ≤ 10

• 1 ≤ dictionary size ≤ 1000

• All words same length

• Words contain only lowercase letters

• Start and end words may not be in dictionary

Sample Input/Output

hit
cog
6
hot
dot
dog
lot
log
cog

5

Explanation

Shortest path: hit → hot → dot → dog → cog. Length = 5 (including start and end).