Minimum Transformations

In this problem, you are given two strings, a starting string ( s ) and an ending string ( t ), along with a list of allowed transformation words. The goal is to determine the minimum number of transformations required to convert ( s ) into ( t ) by changing exactly one character at a time. Each intermediate word must be one of the allowed transformations. Formally, if you denote a transformation as a change where exactly one character differs (i.e. ( \Delta = 1 )), your task is to find the shortest transformation sequence from ( s ) to ( t ), or output -1 if no such sequence exists.

Note: If the starting string is already equal to the ending string, the number of transformations is 0.

inputFormat

The input is given via standard input (stdin). The first line contains two space-separated strings, representing the start string and the end string respectively. The second line contains an integer ( n ), the number of allowed words. Each of the following ( n ) lines contains one allowed word.

outputFormat

Output a single integer on standard output (stdout) representing the minimum number of transformations required to convert the start string to the end string. If the transformation is not possible, output -1.## sample

hit cog
6
hot
dot
dog
lot
log
cog

4