Shortest Word Ladder Transformation

Given two words, a start word and an end word, along with a dictionary of valid words, your task is to find the shortest transformation sequence from the start word to the end word such that:

• Only one letter can be changed at a time.
• Each intermediate word must exist in the dictionary.

If the start word is the same as the end word, the sequence is simply the word itself. Otherwise, if no such transformation is possible, output No ladder exists.

The transformation can be formally described by finding a sequence of words \(w_1, w_2, \dots, w_k\) such that \(w_1 = \text{start}\), \(w_k = \text{end}\), and for each \(1 \leq i < k\), the words \(w_i\) and \(w_{i+1}\) differ in exactly one letter. The goal is to minimize \(k\).

inputFormat

The input is given via standard input and has the following format:

start end
n
word1 word2 ... wordn

Here, start and end are the starting and ending words, n is the number of valid words in the dictionary, and the following line contains n words separated by spaces.

outputFormat

Output the shortest transformation sequence as a series of words separated by a single space. If no valid transformation sequence exists, output No ladder exists.

hit cog
6
hot dot dog lot log cog

hit hot dot dog cog