题目描述

题目译自 European Girls' Olympiad in Informatics 2023 Day2 T1. Carnival Generals

每隔四年，隆德的学生们齐聚一堂，举办隆德狂欢节。几天时间里，公园里搭满了帐篷，各种节庆活动热闹非凡。负责让这一切顺利进行的是一位狂欢节总指挥。

历史上共举办了 $N$ 次狂欢节，每届由一位不同的总指挥负责，总指挥按时间顺序编号为 $0$ 到 $N-1$。每位总指挥 $i$ 都会对他们的前任（即总指挥 $0, 1, \ldots, i-1$）进行评价，发布一个从最好到最差的排名。

下一届隆德狂欢节将在 $2026$ 年举行。在此之前，所有历届总指挥聚在一起拍一张合影。然而，如果总指挥 $i$ 和 $j$ $(i < j)$ 站在一起，而 $i$ 在 $j$ 的排名中严格位于后半部分，场面会显得尴尬。

例如：

• 如果总指挥 $4$ 的排名为 3 2 1 0，则 $4$ 可以站在 $3$ 或 $2$ 旁边，但不能站在 $1$ 或 $0$ 旁边。
• 如果总指挥 $5$ 的排名为 4 3 2 1 0，则 $5$ 可以站在 $4, 3$ 或 $2$ 旁边，但不能站在 $1$ 或 $0$ 旁边。

注意，如果一位总指挥恰好在另一位总指挥的排名中间位置，站在一起是没有问题的。

以下图示展示了样例 1 的情况：总指挥 $5$ 站在 $2$ 和 $3$ 旁边，总指挥 $4$ 仅站在 $2$ 旁边。

你将获得总指挥们发布的排名。你的任务是将总指挥 $0, 1, \ldots, N-1$ 排列成一行，确保相邻的总指挥 $i$ 和 $j$ $(i < j)$ 满足：$i$ 不严格位于 $j$ 排名的后半部分。

输入格式

第一行包含一个正整数 $N$，表示总指挥的数量。

接下来的 $N-1$ 行包含排名。第 $1$ 行是总指挥 $1$ 的排名，第 $2$ 行是总指挥 $2$ 的排名，依此类推，直到总指挥 $N-1$。总指挥 $0$ 没有排名，因为他没有前任可评价。

总指挥 $i$ 的排名是一个包含 $i$ 个整数的列表 $p_{i,0}, p_{i,1}, \ldots, p_{i,i-1}$，其中 $0$ 到 $i-1$ 的每个整数恰好出现一次。$p_{i,0}$ 是 $i$ 认为最好的总指挥，$p_{i,i-1}$ 是最差的。

输出格式

输出一行整数，表示 $0, 1, \ldots, N-1$ 的一个排列，确保每对相邻数字都不违反排名的限制（即相邻的 $i$ 和 $j$ 中，$i$ 不严格位于 $j$ 排名的后半部分）。

可以证明，解总是存在。如果存在多个解，你可以输出任意一个。

6
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0

4 2 5 3 1 0

符合子任务 $1$ 的条件。总指挥 $2$ 和 $3$ 不能站在 $0$ 旁边，总指挥 $4$ 和 $5$ 不能站在 $0$ 和 $1$ 旁边。输出排列 0 1 4 2 3 5 满足条件，如上图所示。

5
0
0 1
0 1 2
0 1 2 3

2 0 4 1 3

符合子任务 $2$ 的条件。总指挥 $2$ 不能站在 $1$ 旁边，总指挥 $3$ 不能站在 $2$ 旁边，总指挥 $4$ 不能站在 $3$ 和 $2$ 旁边。输出排列 0 1 2 3 4 满足条件。

4
0
1 0
0 2 1

3 0 1 2

符合子任务 $3$ 的条件。不能站在一起的总指挥对只有 $(1, 3)$ 和 $(0, 2)$。因此，排列 3 0 1 2 没有冲突。另一个可能的答案是 0 1 2 3。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 1000$
• $0 \leq p_{i,0}, p_{i,1}, \ldots, p_{i,i-1} \leq i-1$（对于 $i = 0, 1, \ldots, N-1$）

详细子任务附加限制及分值如下表所示。