実装難易度★★★☆☆
谜题难度★☆☆☆☆
勇者一行人来到了传说中的圣剑沉睡的冰之洞窟。
迈入地下城最深处的房间时,
眼前出现了一个横向大裂缝,脚下是悬崖。
当勇者望向房间深处时,看见对岸安放着传说中的圣剑。
裂缝中竖立着几根柱子,悬崖和柱子之间架有冰桥。
冰桥可以双向通行,
但一旦通过,就会崩塌而无法再次通行。
勇者一行人能从所在的悬崖渡到安放圣剑的悬崖,
并且还能返回吗?
谜题难度★☆☆☆☆
問題文
迈入地下城最深处的房间时,
眼前出现了一个横向大裂缝,脚下是悬崖。
当勇者望向房间深处时,看见对岸安放着传说中的圣剑。
裂缝中竖立着几根柱子,悬崖和柱子之间架有冰桥。
冰桥可以双向通行,
但一旦通过,就会崩塌而无法再次通行。
勇者一行人能从所在的悬崖渡到安放圣剑的悬崖,
并且还能返回吗?
入力
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
出力例 1
MERASAMU
入力例 2
6 AB CD EF GH IJ KL 6 AB CD CD EF EF GH GH IJ IJ KL KL AB AB GH
出力例 2
ABCDEFGHIJKL