← 返回题目列表

Codeforces · 1343/F

F. 按排序段恢复排列

中文机器翻译题面 查看原题

我们猜测了一个由 $$$n$$$ 整数组成的排列 $$$p$$$。长度 $$$n$$$ 的排列是长度 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次。这个排列对你来说是一个秘密。

对于从 $$$2$$$ 到 $$$n$$$ 的每个位置 $$$r$$$,我们选择了一些其他索引 $$$l$$$ ($$$l < 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$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$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$$$)。

输出

对于每个测试用例,打印答案: $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$,所有 $$$p_i$$$ 应该不同) - 任何合适的排列(即与测试用例输入相对应的任何排列)。

示例

输入 #1

5
6
3 2 5 6
2 4 6
3 1 3 4
2 1 3
4 1 2 4 6
5
2 2 3
2 1 2
2 1 4
2 4 5
7
3 1 2 6
4 1 3 5 6
2 1 2
3 4 5 7
6 1 2 3 4 5 6
3 1 3 6
2
2 1 2
5
2 2 5
3 2 3 5
4 2 3 4 5
5 1 2 3 4 5

输出 #1

3 1 4 6 2 5 
3 2 1 4 5 
2 1 6 3 5 4 7 
1 2 
2 5 3 4 1