しりとり最短終了 Scala編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

paiza 君と kyoko ちゃんは英単語しりとりで遊んでいます。

二人が遊んでいるしりとりのルールは以下の通りです。

・標準的なしりとりと同じように、前の人が言った単語の末尾の文字から始まる単語を言っていく。
・はじめにいくつかの単語で形成される単語群と文字 s と g が与えられる。
・先頭の文字が s となる英単語を 1 単語目として、しりとりを開始する。
・しりとりは、与えられた単語群にある単語のみ使用可能で、一度言った単語はもう一度言うことはできない。
・末尾の文字が g となる英単語を言った場合、しりとりを終了する。

paiza 君と kyoko ちゃんは二人で協力して、このしりとりを最小の単語数で終了させるという遊びをしています。しりとりの開始の文字 s としりとりの終了の文字 g と使用可能な単語群を構成する M 個の単語が与えられます。二人のしりとりで使用された単語数とその単語を順番に出力してください。与えられた単語群からではしりとりを開始できない、または終了できない場合は、inf と出力してください。

入力される値

s g
M
w_1
...
w_M

1 行目に、しりとりの開始の文字を表す s としりとりの終了の文字 g が与えられます。

2 行目に、単語の個数を表す整数 M が与えられます。

i + 1 行目に単語 i を表す文字列が与えられます。(1 ≦ i ≦ M)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 合計 1 行または 2 行出力してください。しりとりを終了できる場合は、1 行目にしりとりを終了させられる最小の単語数を出力し、2 行目にはしりとりを終了するまでに二人が使用した単語を順番に左から半角スペース区切りで出力してください。最小の単語数で終了させられる単語の組み合わせが複数存在する場合は、そのうちのどれかひとつを出力してください。しりとりを開始できない、または終了できない場合は 1 行で inf と出力してください。

また末尾に改行をいれ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

1 ≦ M ≦ 100

s, g は半角英小文字からなる 1 文字の文字列

s ≠ g

w_i は半角英小文字からなる 2 文字以上 15 文字以下の文字列 (1 ≦ i ≦ M)

同じ単語（同じ文字列）は 2 回以上入力されない

入力例1: a r
4
apple
tiger
egg
elephant

出力例1: 3
apple elephant tiger

入力例2: i n
6
apple
gorilla
trumpet
pants
tree
woodpecker

出力例2: inf

問題一覧へ戻る