AT_yuha_c88_d 氷柱の上の聖剣

[problemUrl]: https://atcoder.jp/contests/yuha-c88/tasks/yuha_c88_d 勇者一行は伝説の聖剣が眠っているという氷の洞窟へとやって来た。 ダンジョンの一番奥の部屋へ足を踏み入れると、 目の前には大きな割れ目が横方向に大きく広がり、足元は崖となっていた。 勇者が部屋の奥を見ると、対岸に伝説の聖剣が安置されているのが見えた。 割れ目には柱が何本か立っており、崖や柱の間には氷でできた橋がかかっている。 氷の橋は双方向に行き来することができるが、 一度通ると崩れて通れなくなってしまう。 勇者一行がいる崖から聖剣の安置されている崖へ渡り、 かつ戻ってこられるようなルートはあるだろうか？ 入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ ... $ S_N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ ... $ A_M $ $ B_M $ $ C $ $ D $ - $ 1 $ 行目には崖および柱の総数 $ N\ (3\ ≦\ N\ ≦\ 8) $ が与えられる。 - $ 2 $ 行目からの $ N $ 行のうち $ i $ 行目には $ i $ 番目の崖または柱の名前 $ S_i $ が与えられる。 - $ S_i $ は大文字英アルファベットからなる。 - $ S_i $ の長さ $ |S_i| $ は $ 1\ ≦\ |S_i|\ ≦\ 20 $ を満たす。 - $ i\ ≠\ j $ のとき $ S_i\ ≠\ S_j $ が保証される。 - $ N\ +\ 2 $ 行目には崖や柱の間にかかっている氷の橋の本数 $ M\ (3\ ≦\ M\ ≦\ N\ (N\ -\ 1)\ /\ 2) $ が与えられる。 - $ N\ +\ 3 $ 行目からの $ M $ 行のうち $ i $ 行目には $ i $ 番目の氷の橋の両端の崖または柱の名前 $ A_i $、 $ B_i $ が与えられる。 - ある氷の橋の両端が同一の崖または柱に接続されることがないことが保証される。 - 複数の氷の橋が同一の崖または柱のペアにかかることがないことが保証される。 - $ N\ +\ M\ +\ 3 $ 行目には勇者一行が立っている崖の名前 $ C $ が与えられる。 - $ N\ +\ M\ +\ 4 $ 行目には聖剣が安置されている崖の名前 $ D $ が与えられる。 - $ C\ ≠\ D $ が保証される。 - 入力中では崖と柱が同一視される点に注意せよ。 条件を満たすルート上の崖または柱の名前を結合して $ 1 $ 行に出力せよ。 名前を結合する際、末尾の勇者一行が立っている崖の名前は省略せよ。 複数の解が考えられる場合は通る橋の本数が最小となるルートを出力せよ。 通る橋の本数が最小となる経路が複数ある場合は、 結合後の文字列を辞書順で比較し最も若いものを出力せよ。 出力の末尾に改行を入れること。 条件を満たすルートが必ず存在することが保証されている。 ``` 6 MER A AS U B AM 7 MER A A B B AM MER AS AS AM MER U U AM MER AM ``` ``` MERASAMU ``` ``` 6 AB CD EF GH IJ KL 6 AB CD CD EF EF GH GH IJ IJ KL KL AB AB GH ``` ``` ABCDEFGHIJKL ```

N/A

N/A