该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

寻宝活动中共有 $S$ 个互不相同的藏宝点，每个藏宝点用一个仅由小写英文字母组成的字符串表示。 这些藏宝点按寻宝路线依次排列为 $v_1, v_2, \dots, v_S$，其中 $v_{i+1}$ 紧跟在 $v_i$ 后面。

33DAI 拿到了 $S-1$ 条线索，每条线索是一行两个字符串 $x$ 与 $y$，表示在寻宝路线中 $y$ 紧跟在 $x$ 后面；这些线索的先后顺序被打乱了。

给定 $S$ 与这 $S-1$ 条线索，请你还原出这条寻宝路线。整场活动包含 $T$ 个场景，你需要对每个场景分别还原路线。

输入格式

从文件 hunt.in 读入数据。

输入的第一行包含一个整数 $T$，表示场景数。

接下来依次给出 $T$ 个场景，每个场景的格式为：

• 第一行包含一个整数 $S$，表示该场景中藏宝点的个数；
• 接下来 $S-1$ 行，每行包含两个字符串 $x$ 与 $y$，中间用一个空格隔开，表示 $y$ 紧跟在 $x$ 后面。 这些行的先后顺序是任意的。

输出格式

输出到文件 hunt.out。

按输入顺序依次处理每个场景。对于第 $i$ 个场景（$i$ 从 $1$ 开始）：

• 先输出一行 Scenario #i:；
• 再输出 $S$ 行，每行一个字符串，依次为该场景寻宝路线上的 $S$ 个藏宝点；
• 最后额外输出一个空行。

最后一个场景之后同样要输出这个空行。

2
3
b a
a c
5
zoo bar
bar foo
foo baz
baz qux

Scenario #1:
b
a
c

Scenario #2:
zoo
bar
foo
baz
qux

样例 1 解释

第一个场景的两条线索是「$a$ 紧跟在 $b$ 后面」与「$c$ 紧跟在 $a$ 后面」， 所以路线是 b、a、c。

第二个场景的路线是 zoo、bar、foo、baz、qux，这些线索的输入顺序被打乱了。

本例输出中每个场景之后都有一个空行，最后一个场景之后的空行在代码块里表现为末尾的空行。

1
3
mango apple
apple banana

Scenario #1:
mango
apple
banana

样例 2 解释

路线是 mango、apple、banana。

样例 3

见 hunt3.in 与 hunt3.ans。

样例 4

见 hunt4.in 与 hunt4.ans。

数据范围

对于所有测试数据，保证：

• $1 \le T \le 1000$；
• $3 \le S \le 333$；
• 单个测试文件中所有场景的 $S$ 之和不超过 $4 \times 10^4$；
• 每个字符串的长度在 $1$ 到 $24$ 之间，且仅由小写英文字母 a 到 z 组成；
• 同一个场景内的 $S$ 个字符串互不相同；
• 给出的 $S-1$ 条线索恰好构成一条依次经过该场景全部 $S$ 个藏宝点的链， 也就是说，路线一定存在且唯一。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。