如果 $$$n$$$ 数字序列包含从 $$$1$$$ 到 $$$n$$$ 的所有整数恰好一次,则该序列称为排列。例如,序列 [$$$3, 1, 4, 2$$$]、[$$$1$$$] 和 [$$$2,1$$$] 是排列,但 [$$$1,2,1$$$]、[$$$0,1$$$] 和 [$$$1,3,4$$$] 不是排列。
Kristina 有 $$$p$$$ 个 $$$n$$$ 元素的排列。她在白板上写了 $$$n$$$ 次,如下:
- 在第 $$$i$$$ ($$$1 \le i \le n)$$$ 处写入排列时,她跳过了元素 $$$p_i$$$
例如,假设 Kristina 的排列 $$$p$$$ = $$$[4,2,1,3]$$$ 长度为 $$$4$$$。然后她做了以下事情:
1. 编写序列 $$$[2, 1, 3]$$$,跳过原始排列中的元素 $$$p_1=4$$$。
2. 编写序列 $$$[4, 1, 3]$$$,跳过原始排列中的元素 $$$p_2=2$$$。
3. 编写序列 $$$[4, 2, 3]$$$,跳过原始排列中的元素 $$$p_3=1$$$。
4. 编写序列 $$$[4, 2, 1]$$$,跳过原始排列中的元素 $$$p_4=3$$$。
你知道白板上写的所有 $$$n$$$ 序列,但你不知道它们的书写顺序。它们以任意顺序给出。从它们重建原始排列。
例如,如果您知道序列 $$$[4, 2, 1]$$$, $$$[4, 2, 3]$$$, $$$[2, 1, 3]$$$, $$$[4, 1, 3]$$$,则原始排列将为 $$$p$$$ = $$$[4, 2, 1, 3]$$$。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 100$$$)。
接下来是 $$$n$$$ 行,每行恰好包含 $$$n-1$$$ 整数并描述写在白板上的序列之一。
保证所有序列都可以从某种排列 $$$p$$$ 中获得,并且所有输入集的总和 $$$n^2$$$ 不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出排列 $$$p$$$,以便可以从中获得给定的 $$$n$$$ 序列。
保证答案存在并且是唯一的。换句话说,对于每个测试用例,所需的排列肯定存在。
示例
输入 #1
5 4 4 2 1 4 2 3 2 1 3 4 1 3 3 2 3 1 3 1 2 5 4 2 1 3 2 1 3 5 4 2 3 5 4 1 3 5 4 2 1 5 4 2 3 4 1 3 4 1 2 3 1 2 4 3 2 1 1 3 2 3
输出 #1
4 2 1 3 1 2 3 4 2 1 3 5 1 2 3 4 2 1 3
注意
第一个测试用例在问题陈述中进行了描述。
在第二个测试用例中,序列以正确的顺序写入。