题目描述

一个长度为 $n$ 的数列被称为排列，如果它恰好包含 $1$ 到 $n$ 的所有整数各一次。例如，数列 $[3, 1, 4, 2]$、$[1]$ 和 $[2, 1]$ 是排列，但 $[1, 2, 1]$、$[0, 1]$ 和 $[1, 3, 4]$ 不是排列。

Kristina 有一个长度为 $n$ 的排列 $p$。她在白板上写下了 $n$ 次这个排列，每次写的时候：

• 在第 $i$ 次（$1 \le i \le n$）写的时候，她跳过了第 $i$ 个元素 $p_i$。

所以，她总共写下了 $n$ 个长度为 $n-1$ 的数列。例如，假设 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$ 个数列可以由它得到。

保证答案存在且唯一。换句话说，对于每个测试用例，所需的排列一定存在且只有一个。

说明/提示

第一个测试用例在题目描述中已经给出。

在第二个测试用例中，数列的顺序就是正确的顺序。

由 ChatGPT 4.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

4 2 1 3 
1 2 3 
4 2 1 3 5 
1 2 3 4 
2 1 3