CF1343F Restore the Permutation by Sorted Segments

我们猜测了一个由 $n$ 个整数组成的排列 $p$。长度为 $n$ 的排列是指长度为 $n$ 的数组，其中每个 $1$ 到 $n$ 的元素恰好出现一次。这个排列对你来说是一个秘密。 对于每个位置 $r$，其中 $2 \le r \le n$，我们选择了另一个下标 $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$ 行以一个整数 $k_i$（$2 \le k_i \le n$）开头，表示第 $i$ 个区间的长度。接下来有 $k_i$ 个整数，均为升序排列，且在 $1$ 到 $n$ 之间，且在该行内互不相同。 保证对于每个测试用例都存在所需的排列。 还保证所有测试用例中 $n$ 的总和不超过 $200$（$\sum n \le 200$）。

对于每个测试用例，输出一行答案：$n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，所有 $p_i$ 互不相同），即任意一个符合条件的排列。

由 ChatGPT 4.1 翻译