Premutation

题意翻译

现有一个 $1\sim n$ 的排列，它有到 $n$ 个不同的长度为 $n - 1$ 的子序列。 给定这些子序列，请还原原排列。保证有唯一解。 多组数据，$1\leq T \leq 10^4,3\leq n \leq 100,\sum n^2\leq 2\times 10^5$。 translated by @[StayAlone](https://www.luogu.com.cn/user/409236)

题目描述

A sequence of $ n $ numbers is called permutation if it contains all integers from $ 1 $ to $ n $ exactly once. For example, the sequences \[ $ 3, 1, 4, 2 $ \], \[ $ 1 $ \] and \[ $ 2,1 $ \] are permutations, but \[ $ 1,2,1 $ \], \[ $ 0,1 $ \] and \[ $ 1,3,4 $ \] — are not. Kristina had a permutation $ p $ of $ n $ elements. She wrote it on the whiteboard $ n $ times in such a way that: - while writing the permutation at the $ i $ -th ( $ 1 \le i \le n) $ time she skipped the element $ p_i $ So, she wrote in total $ n $ sequences of length $ n-1 $ each.For example, suppose Kristina had a permutation $ p $ = $ [4,2,1,3] $ of length $ 4 $ . Then she did the following: 1. Wrote the sequence $ [2, 1, 3] $ , skipping the element $ p_1=4 $ from the original permutation. 2. Wrote the sequence $ [4, 1, 3] $ , skipping the element $ p_2=2 $ from the original permutation. 3. Wrote the sequence $ [4, 2, 3] $ , skipping the element $ p_3=1 $ from the original permutation. 4. Wrote the sequence $ [4, 2, 1] $ , skipping the element $ p_4=3 $ from the original permutation. You know all $ n $ of sequences that have been written on the whiteboard, but you do not know the order in which they were written. They are given in arbitrary order. Reconstruct the original permutation from them. For example, if you know the sequences $ [4, 2, 1] $ , $ [4, 2, 3] $ , $ [2, 1, 3] $ , $ [4, 1, 3] $ , then the original permutation will be $ p $ = $ [4, 2, 1, 3] $ .

输入输出格式

输入格式

The first line of input data contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 3 \le n \le 100 $ ). This is followed by $ n $ lines, each containing exactly $ n-1 $ integers and describing one of the sequences written out on the whiteboard. It is guaranteed that all sequences could be obtained from some permutation $ p $ , and that the sum $ n^2 $ over all input sets does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output on a separate line a permutation $ p $ such that the given $ n $ sequences could be obtained from it. It is guaranteed that the answer exists and it is the only one. In other words, for each test case the required permutation is sure to exist.

输入输出样例

输入样例 #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

说明

The first test case is described in the problem statement. In the second test case, the sequences are written in the correct order.

**题目大意：**
题目要求根据给出的子序列还原一个1到n的排列。Kristina有一个长度为n的排列p，并按照以下规则将其写了n次到白板上：在第i次写排列时，跳过元素p_i。所以总共写了n个长度为n-1的序列。现在已知这n个序列，但不知道它们的顺序。需要从这些序列中重构出原始排列。

**输入输出数据格式：**
- **输入格式：**
- 第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行输入一个整数n（3≤n≤100）。
- 接下来的n行，每行输入n-1个整数，描述白板上的一个序列。
- 保证所有序列都可以从某个排列p得到，且所有输入集合的n^2之和不超过2×10^5。
- **输出格式：**
- 对于每个测试用例，输出一行，包含一个排列p，使得给定的n个序列可以从中得到。
- 保证答案存在且唯一。

**输入输出样例：**
- **输入样例：**
```
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
```**题目大意：** 题目要求根据给出的子序列还原一个1到n的排列。Kristina有一个长度为n的排列p，并按照以下规则将其写了n次到白板上：在第i次写排列时，跳过元素p_i。所以总共写了n个长度为n-1的序列。现在已知这n个序列，但不知道它们的顺序。需要从这些序列中重构出原始排列。 **输入输出数据格式：** - **输入格式：** - 第一行输入一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行输入一个整数n（3≤n≤100）。 - 接下来的n行，每行输入n-1个整数，描述白板上的一个序列。 - 保证所有序列都可以从某个排列p得到，且所有输入集合的n^2之和不超过2×10^5。 - **输出格式：** - 对于每个测试用例，输出一行，包含一个排列p，使得给定的n个序列可以从中得到。 - 保证答案存在且唯一。 **输入输出样例：** - **输入样例：** ``` 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 ```