勇者一行来到了传说中圣剑沉睡的冰之洞窟。

当他们踏入地下城最深处的房间时，眼前出现了一道横向巨大的裂缝，脚下则是悬崖。勇者望向房间深处，看到对岸安放着传说中的圣剑。裂缝中竖立着几根柱子，悬崖和柱子之间架有冰桥。冰桥可以双向通行，但每次通过后就会崩塌，无法再次通行。

请判断，勇者一行是否存在一条可以从他们所在的悬崖出发，经过冰桥到达圣剑所在的悬崖，并且还能返回原处的路线。

输入格式如下。

• 第 $1$ 行输入悬崖及柱子的总数 $N\ (3 \leq N \leq 8)$。
• 接下来 $N$ 行，第 $i$ 行输入第 $i$ 个悬崖或柱子的名字 $S_i$。
  • $S_i$ 由大写英文字母组成。
  • $1 \leq |S_i| \leq 20$。
  • 保证 $i \neq j$ 时 $S_i \neq S_j$。
• 第 $N+1$ 行输入冰桥的数量 $M\ (3 \leq M \leq N(N-1)/2)$。
• 接下来 $M$ 行，第 $i$ 行输入第 $i$ 条冰桥两端的悬崖或柱子的名字 $A_i$、$B_i$。
  • 保证每条冰桥的两端不同。
  • 保证同一对悬崖或柱子之间没有多条冰桥。
• 第 $N+M+2$ 行输入勇者一行所在悬崖的名字 $C$。
• 第 $N+M+3$ 行输入圣剑所在悬崖的名字 $D$。
  • 保证 $C \neq D$。

注意，输入中的“悬崖”和“柱子”没有区别。

请输出满足条件的路线，将路径上经过的悬崖或柱子的名字依次连接成一个字符串，输出一行。连接时，末尾的勇者一行所在悬崖的名字不输出。

如果有多条满足条件的路线，请输出经过冰桥数量最少的路线。如果经过冰桥数量最少的路线有多条，请输出连接后字符串字典序最小的那一条。

输出末尾需换行。

保证一定存在满足条件的路线。

输入格式

见上文描述。

输出一行，表示满足条件的路线，将路径上经过的悬崖或柱子的名字依次连接成一个字符串，末尾不包含勇者一行所在悬崖的名字。末尾需换行。

无。

由 ChatGPT 4.1 翻译