题目描述

从前有一天，Mary 买了一张从某地飞往某地的单程机票，其中包含一些航班中转。

例如：SFO->DFW DFW->JFK JFK->MIA MIA->ORD。

显然，在一个城市中转两次或更多次没有任何意义，所以 Mary 不会这样做。

不幸的是，她收到机票后把机票弄乱了，并且忘记了机票的顺序。

请帮助 Mary 重新排列这些机票，使它们按正确的顺序排列。

输入格式

第一行包含测试用例的个数 $T$，随后是 $T$ 个测试用例。对于每个测试用例，首先是一个整数 $N$。接下来是 $N$ 张机票的信息。每张机票由接下来的两行组成，分别是一个航班的出发地和目的地。

输出格式

对于每个测试用例，输出一行形如 Case #x: itinerary 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），itinerary是排好序的机票列表，代表实际行程。行程中的每个航班段应以 "出发地-目的地" 机场代码对的形式输出。

2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA

Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD

提示

（下方为样例中第二个测试用例的航班段展示） MIA-ORD, DFW-JFK, SFO-DFW, JFK-MIA

限制

$1 \le T \le 100$。

对于每个测试用例，输入中的机票是从 Mary 购买的整个行程中打乱得到的。换言之，保证可以恢复成一个合法的行程。

小数据集（测试集 1 - 可见）

$1 \le N \le 100$。

大数据集（测试集 2 - 隐藏）

$1 \le N \le 10^4$。

翻译由 DeepSeek V4 Pro 完成