题目内容

排查骨干网上的报文时，运维手里会有一张跳转表。表中第 $p$ 项写作 $hops[p] = [u, v]$，表示报文从设备 $u$ 发到设备 $v$。

需要把表里的跳转排成一条走法。这些跳转同属从 $Core\text{-}SW\text{-}01$ 出发的一条流，因此走法的第一个点必须是 $Core\text{-}SW\text{-}01$。若有若干条都合法的走法，按设备名的字典序取出最小的那一条。

比如 $["Core\text{-}SW\text{-}01", "N\text{-}A"]$ 会排在 $["Core\text{-}SW\text{-}01", "N\text{-}B"]$ 前面。

保证至少能排出一种合法走法。每条跳转都要恰好用一次，既不能漏也不能重复。

业务背景

机房里的设备会连成有向图。追异常报文或改拓扑时，要把报文经过各台机器的先后顺序写清楚。本题就是对照事先配好的跳转表，把真实走过的设备序列还原出来。

输入描述

若干行，每行两个字符串 $u$、$v$，表示一条从 $u$ 指向 $v$ 的跳转；行数就是跳转条数。

示例如下：

N-A N-B
Core-SW-01 N-A
Dev-P Dev-Q
N-B Dev-P

输出描述

上面这份表示例对应的走法是：

Core-SW-01 N-A N-B Dev-P Dev-Q

把走法中的设备名用空格隔开，输出成一行。

样例1

输入

Core-SW-01 R-B
Core-SW-01 R-A
R-A R-C
R-C Core-SW-01
R-B R-A

输出

Core-SW-01 R-A R-C Core-SW-01 R-B R-A

说明

从 $Core\text{-}SW\text{-}01$ 出发，先走到 $R\text{-}A$，再经 $R\text{-}C$ 回到起点，最后走 $R\text{-}B$ 再到 $R\text{-}A$，每条跳转恰好一次。

另一条合法走法是 $Core\text{-}SW\text{-}01\ R\text{-}B\ R\text{-}A\ R\text{-}C\ Core\text{-}SW\text{-}01\ R\text{-}A$，但第二个点 $R\text{-}B$ 比 $R\text{-}A$ 大，字典序更靠后。

提示：同一点若还剩若干条未用跳转，应优先走终点名字更小的那条。

约束条件

• $1 \le m \le 300$，其中 $m$ 为 $hops$ 的条数
• 每条 $hops[p]$ 恰好含两个端点
• $u$ 与 $v$ 仅由大小写英文字母、数字、短横线构成
• 每个设备名长度介于 $1$ 与 $20$ 之间
• 一定存在从 $Core\text{-}SW\text{-}01$ 出发、用尽全部跳转的走法