Minimum Transformation Steps

You are given a starting word \( S \) and an ending word \( T \), along with a list of bidirectional word pairs. Each pair indicates a valid transformation from one word to the other. In one step, you may transform a word into a connected word via a given pair.

Your task is to determine the minimum number of steps required to transform \( S \) into \( T \) using these valid transformations. If no such sequence exists, output -1. Note that if \( S = T \), the number of steps required is 0.

Explanation:

• Each transformation step changes the current word to a word that is directly connected via the given pairs.
• The transformation pairs are bidirectional.
• You must use the given pairs, and each valid transformation must exactly follow one of these pairs.

The task is equivalent to finding the shortest path in an undirected graph where nodes represent words and edges represent allowed transformations.

Formula: If we denote the number of steps as \( d(S, T) \), then after \( k \) transformations, we have: \[ S \to w_1 \to w_2 \to \cdots \to w_k = T \] The goal is to minimize \( k \).

inputFormat

The input is read from stdin and has the following format:

S
T
n
word1_1 word1_2
word2_1 word2_2
... 
wordn_1 wordn_2

Where:

• S is the starting word.
• T is the ending word.
• n is the number of word pairs.
• The next n lines each contain two words separated by space representing a bidirectional transformation pair.

outputFormat

The output is written to stdout and should be a single integer representing the minimum number of transformation steps from \( S \) to \( T \). If there is no valid transformation sequence, output -1.

## sample

hit
cog
4
hit hot
hot dot
dot dog
dog cog

4