Word Ladder Transformation Sequences

Given two words, beginWord and endWord, and a list of valid words, you are to find all the shortest transformation sequences from beginWord to endWord.

A transformation is defined by changing exactly one character at a time, and each intermediate word must exist in the word list. If no valid transformation exists, then the output should indicate so.

Note: The transformation sequence does not need to be unique, but only the ones with the minimum number of steps should be reported.

Example:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: Two sequences:

• hit hot dot dog cog
• hit hot lot log cog

If no transformation is possible, output 0.

Input/Output format details are provided below.

inputFormat

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

T
beginWord1 endWord1 n1
word1 word2 ... word_n1
beginWord2 endWord2 n2
word1 word2 ... word_n2
...
beginWordT endWordT nT
word1 word2 ... word_nT

Where:

• T is the number of test cases.
• For each test case, the first line contains the beginWord, endWord, and an integer n indicating the number of words in the list.
• The next line contains n words separated by spaces.

outputFormat

For each test case, output the result to stdout in the following format:

• If at least one valid transformation sequence exists, first output an integer S on a new line which denotes the number of shortest transformation sequences found, followed by S lines where each line is one sequence. The words in a sequence are separated by a single space.
• If no valid transformation exists, output a single line with 0.

The outputs for multiple test cases should be printed sequentially without any extra delimiters.

## sample

3
hit cog 6
hot dot dog lot log cog
hit cog 3
hot dot dog
a c 3
a b c

2
hit hot dot dog cog
hit hot lot log cog
0
1
a c

</p>