Background

Day 2 Problem A.

Translated from EGOI2023 carnival。

Problem Description

Every four years, students in Lund gather and host the Lund Carnival. Over a few days, the park fills up with tents and many kinds of celebrations are held. The person responsible for organizing all of this is called the Carnival General.

There are $N$ carnivals, each with a different general. These generals are numbered from $0$ to $N-1$ in chronological order. Each general $i$ gives their opinion on previous generals: they publish a ranking of generals $0,1,\cdots,i-1$ from best to worst.

The next Lund Carnival will be held in 2026. During that time, all former carnival generals got together to take a group photo. However, it will be awkward if generals $i$ and $j$ (where $i < j$) end up standing next to each other, and $i$ is ranked strictly in the bottom half of the ranking given by $j$.

For example:

• If the ranking given by general $4$ is 3 2 1 0, then $4$ may stand next to $3$ or $2$, but may not stand next to $1$ or $0$.
• If the ranking given by general $5$ is 4 3 2 1 0, then $5$ may stand next to $4,3,2$, but may not stand next to $1$ or $0$.

The figure below shows Sample $1$. In it, general $5$ stands next to generals $2$ and $3$, and general $4$ stands only next to general $2$.

You know all the rankings given by the generals. Your task is to arrange all generals $0,1,\cdots,N-1$ in a line such that whenever $i$ and $j$ stand next to each other (where $i < j$), then $i$ is not ranked strictly in the bottom half of the ranking given by $j$.

Input Format

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

The next $N-1$ lines contain all rankings. The first of these lines is the ranking given by general $1$, the second is the ranking given by general $2$, and so on up to general $N-1$. General $0$ is not included in the input, because general $0$ has no previous generals to rank.

The ranking of general $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, in the ranking of general $i$, $p_{i,0}$ is the best general and $p_{i,i-1}$ is the worst general.

Output Format

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

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

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

4 2 5 3 1 0

5
0
0 1
0 1 2
0 1 2 3

2 0 4 1 3

4
0
1 0
0 2 1

3 0 1 2

Hint

Sample $1$ Explanation

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

Sample $2$ Explanation

Sample $2$ satisfies the requirements of Subtask 2. In the sample, general $2$ cannot stand next to general $1$, general $3$ cannot stand next to general $2$, and general $4$ cannot stand next to generals $3$ and $2$.

Sample $3$ Explanation

Sample $3$ satisfies the requirements of Subtask 3. In the sample, only the two pairs $(1,3)$ and $(0,2)$ of generals cannot stand next to each other. Therefore, if the arrangement is 3 0 1 2, there will be no conflict. Another possible answer is 0 1 2 3.

Constraints

For all testdata, $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 general $i$ is $i-1,i-2,\cdots,0$.
• Subtask 2 ($23$ points): the ranking given by general $i$ is $0,1,\cdots,i-1$.
• Subtask 3 ($29$ points): $N\le 8$.
• Subtask 4 ($37$ points): no additional constraints.

Translated by ChatGPT 5