倒影

• 时间限制：$2$ 秒
• 空间限制：$512\text{ MB}$

题目描述

有一个长度为 $n$ 的隐藏的 $1 \sim n$ 的排列 $p$。我们把 $p$ 中的元素排列在一个环上，也就是说对任何整数 $k$，都有 $p_k = p_{(k - 1) \bmod n + 1}$。

对于每个 $2 \leq i \leq n$，给出 $p$ 中值为 $i$ 的元素的接下来 $i - 1$ 个元素组成的集合 $S_i$。形式化地，若 $p_k = i$，则我们以任意顺序给出 $S_i = \{p_{k+1}, p_{k+2}, \dots, p_{k+i-1}\}$ 这个集合中的所有元素。

你需要还原任何一个符合所有条件的排列。数据保证有解。

输入格式

本题包含多组测试数据。

输入第一行包含一个整数 $T$ 表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个整数 $n$。
• 接下来 $n - 1$ 行，第 $i$ 行包含 $i$ 个整数，表示 $S_{i+1}$ 的所有元素。

输出格式

对于每组数据，输出一行一个长度为 $n$ 的排列，表示你还原的排列 $p$。

样例输入

6
2
1
3
1
1 2
3
3
1 2
4
4
4 2
3 1 2
8
6
5 7
3 5 7
7 1 8 2
4 3 5 7 1
1 8 2 6 4 3
2 6 4 3 5 7 1
11
1
2 4
8 2 1
9 7 10 6
9 7 4 3 11
4 3 9 11 2 1
5 11 6 3 7 10 9
4 3 11 1 8 5 2 10
2 7 8 3 1 4 6 11 9
7 4 2 6 1 3 5 8 10 9

样例输出

1 2
3 2 1
1 2 3
1 3 2 4
1 8 2 6 4 3 5 7
10 6 7 9 11 3 4 2 1 8 5

样例解释

对于第一组数据，唯一给出的信息为值为 $2$ 的元素的下一个元素的值为 $1$，因此 $p = [1, 2]$ 符合条件。可以得到 $p = [2, 1]$ 同样符合条件。

对于第二组数据，符合条件的排列还有 $p = [1, 3, 2]$ 和 $p = [2, 1, 3]$。

数据规模与约定

本题使用捆绑测试。 各个子任务对应的特殊数据范围如下：

• Subtask 1（13 分）：$n \le 10$。
• Subtask 2（9 分）：$n \le 20$。
• Subtask 3（17 分）：$n \le 50$。
• Subtask 4（21 分）：$n \le 100$。
• Subtask 5（19 分）：$n \le 200$。
• Subtask 6（21 分）：无特殊限制。

对于所有数据，满足 $1 \le T \le 10$，$1 \le n \le 1000$，数据保证有解。