C - ダブレット Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

2013.01.19 21:28　入力の制限に「単語は英小文字のみで構成される」ことを追記しました。
2013.01.20 21:03　入力の制限の、単語リストに含まれる単語の条件を訂正しました。

問題文

ヨーロッパでよく知られている言葉遊びとして「ダブレット」がある。
これは、ある単語から別の単語へ、一文字ずつ文字を変えていくことによって変換する、というものである。
例えば、head を tail に変える場合、4 単語を経由し、head→heal→teal→tell→tall→tailと変換することができる。
与えられた単語リストを用いてダブレットをするとき、変換する過程を表示するプログラムを作成せよ。
ただし、変換することが可能であるならば、その変換回数は最小でなければならない。

入力

入力は以下の形式で標準入力から与えられる。 
first last
N
s_{0}
s_{1}
:
s_{N-1}
  1. 1 行目に最初の単語 first と、最後の単語 last が半角スペースで区切られて与えられる。
  2. 2 行目に単語リストに含まれる単語の個数を表す整数 N(1≦N≦1,000) が与えられる。
  3. 3 行目から N+2 行目までの N 行は単語リストが与えられる。
    • 単語リストの中に同じ単語が複数含まれることもあり、単語リストの中に最初の単語 first と、最後の単語 last が含まれることもある。
    • しかし、最初の単語 first と、最後の単語 last が同じパターンは入力としてありうる。
    • 各単語の文字数は全て等しく、1 文字以上 30 文字以下とする。
    • 各単語は英小文字 a-z のみで構成される。

出力

変換が可能な場合、 1 行目に変換に用いる単語の個数 k を出力し、続く k+2 行で最初の単語と最後の単語を含めた変換過程を出力せよ。
ただし、k が最小となる変換過程でならなければならない。
変換過程は 1 行につき 1 つの単語のみ出力すること。
変換過程が複数ある場合、どれを出力しても構わない。
最初と最後の単語が同じ単語である場合は k=0 である。
変換できない場合には、-1 とだけ出力せよ。
また、出力の最後には改行をいれること。

入力例 1

eye lid
4
lie
die
did
dye

出力例 1

3
eye
dye
die
lie
lid
  1. 1 行目には変換に用いる単語数である 3 を出力する。
  2. 2 行目以降は変換する過程を出力する。
    • eye ... 最初の単語 first である。
    • dye ... eyeの 1 文字目であるeをdへ変換した。
    • die ... dyeの 2 文字目であるyをiへ変換した。
    • lie ... dieの 1 文字目であるdをlへ変換した。
    • lid ... lieの 3 文字目であるeをdへ変換した。また、最後の単語 last なので終了する。

入力例 2

eye eye
4
lie
die
did
dye

出力例 2

0
eye
eye
  • 最初の単語 first と、最後の単語 last が一致するので、変換に用いる単語数は 0 である。
  • 最初の単語 first と、最後の単語 last をそれぞれ 1 行で出力して終了する。

入力例 3

eye lid
4
lie
lip
did
dye

出力例 3

-1
  • 与えられた単語リストのみを用いてeyeからlidへ変換することができないので、-1を出力する。