Word Ladder Transformation

Given two words start_word and end_word and a list of words, your task is to find all the shortest transformation sequences (word ladders) from start_word to end_word. In each transformation, exactly one character can be changed and the resulting intermediate word must exist in the given word list.

Mathematically, for any valid transformation sequence \( w_0, w_1, \ldots, w_k \), it must satisfy \( d(w_i, w_{i+1}) = 1 \) for all \( 0 \leq i < k \), where \( d(\cdot,\cdot) \) denotes the Hamming distance.

If no valid transformation exists, output an empty list []. The output ladders should be the shortest possible sequences.

inputFormat

The input is read from stdin with the following format:

1. The first line contains the starting word start_word.
2. The second line contains the target word end_word.
3. The third line contains an integer n, which is the number of words in the word list.
4. The following n lines each contain a word that belongs to the word list.

outputFormat

The output should be printed to stdout as a Python-style list of lists. Each inner list represents one shortest transformation sequence formatted as shown in the examples. If no such sequence exists, output an empty list [].

hit
cog
6
hot
dot
dog
lot
log
cog

[["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]]