CF1343F.Restore the Permutation by Sorted Segments

We guessed a permutation $p$ consisting of $n$ integers. The permutation of length $n$ is the array of length $n$ where each element from $1$ to $n$ appears exactly once. This permutation is a secret for you.

For each position $r$ from $2$ to $n$ we chose some other index $l$ ($l \lt r$) and gave you the segment $p_l, p_{l + 1}, \dots, p_r$ in sorted order (i.e. we rearranged the elements of this segment in a way that the elements of this segment are sorted). Thus, you are given exactly $n-1$ segments of the initial permutation but elements inside each segment are sorted. The segments are given to you in random order.

For example, if the secret permutation is $p=[3, 1, 4, 6, 2, 5]$ then the possible given set of segments can be:

• $[2, 5, 6]$
• $[4, 6]$
• $[1, 3, 4]$
• $[1, 3]$
• $[1, 2, 4, 6]$

Your task is to find any suitable permutation (i.e. any permutation corresponding to the given input data). It is guaranteed that the input data corresponds to some permutation (i.e. such permutation exists).

You have to answer $t$ independent test cases.

我们猜出了一个由 $n$ 个整数组成的排列 $p$。长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。该排列对你而言是保密的。

对于每个位置 $r$（从 $2$ 到 $n$），我们选择另一个下标 $l$（满足 $l \lt r$），并将子段 $p_l, p_{l + 1}, \dots, p_r$ 按升序排序后提供给你（即：我们将该子段中的元素重新排列，使其成为有序序列）。因此，你恰好获得 $n-1$ 个原始排列的子段，但每个子段内部的元素是已排序的。这些子段以随机顺序提供给你。

例如，若秘密排列为 $p=[3, 1, 4, 6, 2, 5]$，则可能给出的子段集合为：

• $[2, 5, 6]$
• $[4, 6]$
• $[1, 3, 4]$
• $[1, 3]$
• $[1, 2, 4, 6]$

你的任务是找出任意一个符合条件的排列（即：任一与所给输入数据对应的排列）。题目保证输入数据对应至少一个排列（即：这样的排列一定存在）。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($2 \le n \le 200$) — the length of the permutation.

The next $n-1$ lines describe given segments.

The $i$-th line contains the description of the $i$-th segment. The line starts with the integer $k_i$ ($2 \le k_i \le n$) — the length of the $i$-th segment. Then $k_i$ integers follow. All integers in a line are distinct, sorted in ascending order, between $1$ and $n$, inclusive.

It is guaranteed that the required $p$ exists for each test case.

It is also guaranteed that the sum of $n$ over all test cases does not exceed $200$ ($\sum n \le 200$).

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 200$），表示排列的长度。

接下来的 $n-1$ 行描述给定的区间。

第 $i$ 行描述第 $i$ 个区间。该行以一个整数 $k_i$（$2 \le k_i \le n$）开头，表示第 $i$ 个区间的长度；随后是 $k_i$ 个整数。每行中的所有整数互不相同，按升序排列，且均在 $1$ 到 $n$ 之间（含端点）。

保证对每个测试用例均存在满足要求的排列 $p$。

还保证所有测试用例的 $n$ 值之和不超过 $200$（即 $\sum n \le 200$）。

For each test case, print the answer: $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ should be distinct) — any suitable permutation (i.e. any permutation corresponding to the test case input).

对于每个测试用例，输出答案：$n$ 个整数 $p_1, p_2, \dots, p_n$（其中 $1 \le p_i \le n$，且所有 $p_i$ 互不相同）——任一满足条件的排列（即任一与该测试用例输入相对应的排列）。