Problem Background

Day 2 Problem A.

The problem statement is translated from EGOI2023 carnival.

Problem Description

Every four years, students in Lund gather to organize the Lund Carnival. Over a few days, the parks are filled with tents and various celebrations. The person in charge of organizing all this is known as the Carnival Manager.

There are $N$ carnivals, each with a different manager. These managers are numbered sequentially from $0$ to $N-1$. Each manager $i$ provides their evaluation of their predecessors, publishing a ranking from best to worst of managers $0, 1, \cdots, i-1$.

The next Lund Carnival will be held in 2026. In the meantime, all former carnival managers gathered together for a group photo. However, if managers $i$ and $j$ (where $i < j$) end up next to each other, and $i$ is strictly in the second half of $j$'s ranking, it would be awkward.

For example:

• If manager $4$ gives the ranking 3 2 1 0, then $4$ can stand next to $3$ or $2$, but not next to $1$ or $0$.
• If manager $5$ gives the ranking 4 3 2 1 0, then $5$ can stand next to $4, 3, 2$, but not next to $1$ or $0$.

The figure below shows Sample 1. Here, manager $5$ stands next to managers $2$ and $3$, and manager $4$ only stands next to manager $2$.

You are given the rankings provided by all managers. Your task is to arrange all managers $0, 1, \cdots, N-1$ in a row such that if $i$ and $j$ are next to each other (where $i < j$), then $i$ is not strictly in the second half of $j$'s ranking.

Input Format

The first line contains an integer $N$, the total number of managers.

The next $N-1$ lines contain all the rankings. The first line is the ranking given by manager $1$, the second line is the ranking given by manager $2$, and so on up to manager $N-1$. Manager $0$ is not included in the input because manager $0$ has no predecessors to rank.

The ranking given by manager $i$ is a list of length $i$ $p_{i,0}, p_{i,1}, \cdots, p_{i,i-1}$, where each integer from $0$ to $i-1$ appears exactly once. Specifically, according to manager $i$'s ranking, $p_{i,0}$ is the best manager, and $p_{i,i-1}$ is the worst manager.

Output Format

Output a list of integers, a permutation of $0, 1, \cdots, N-1$, such that for every pair of adjacent integers, one is not in the second half of the other's ranking.

It can be proven that a solution always exists. If there are multiple solutions, you can output any one.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4 2 5 3 1 0

Sample Input #2

5
0
0 1
0 1 2
0 1 2 3

Sample Output #2

2 0 4 1 3

Sample Input #3

4
0
1 0
0 2 1

Sample Output #3

3 0 1 2

Notes

Sample 1 Explanation

Sample 1 meets the requirements of Subtask 1. In the sample, managers $2$ and $3$ cannot stand next to manager $0$, and managers $4$ and $5$ cannot stand next to managers $0$ and $1$. The sample output is shown in the figure above.

Sample 2 Explanation

Sample 2 meets the requirements of Subtask 2. In the sample, manager $2$ cannot stand next to manager $1$, manager $3$ cannot stand next to manager $2$, and manager $4$ cannot stand next to managers $3$ and $2$.

Sample 3 Explanation

Sample 3 meets the requirements of Subtask 3. In the sample, only pairs $(1, 3)$ and $(0, 2)$ cannot stand next to each other. Therefore, arranging them as 3 0 1 2 will not cause any conflicts. Another possible answer is 0 1 2 3.

Data Range

For all data, $2 \le N \le 10^3$, $0 \le p_{i,0}, p_{i,1}, \cdots, p_{i,i-1} \le i-1$.

• Subtask 1 (11 points): The ranking given by manager $i$ is $i-1, i-2, \cdots, 0$.
• Subtask 2 (23 points): The ranking given by manager $i$ is $0, 1, \cdots, i-1$.
• Subtask 3 (29 points): $N \le 8$.
• Subtask 4 (37 points): No additional constraints.

见题面 Input 部分

见题面 Output 部分