European Girls' Olympiad in Informatics: 2023 Day 2 Problem 1

Every four years, the students of Lund come together to organize the Lund Carnival. For a few days, a park fills with tents where all kinds of festive activities take place. The person in charge of making this happen is the carnival general.

In total, there have been $N$ carnivals, each with a different general. The generals are numbered from $0$ to $N-1$ in chronological order. Every general $i$ has given their opinion on how good their predecessors were, by publishing a ranking of the generals $0,1,\dots ,i-1$ in order from best to worst.

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

For example:

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

Note that it is fine if one general is exactly in the middle of another's ranking.

The following figure illustrates sample 1. Here, general $5$ stands next to generals $2$ and $3$, and general $4$ stands next to general $2$ only.

You are given the rankings that the generals published. Your task is to arrange the generals $0,1,\dots ,N-1$ in a row, so that if $i$ and $j$ are adjacent (where $i<j$) then $i$ is not strictly in the second half of $j$'s ranking.

Input Specification

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

The following $N-1$ lines contain the rankings. The first of these lines contains general $1$'s ranking, the second line contains general $2$'s ranking, and so on until general $N-1$. General $0$ is absent since general $0$ didn't have any predecessors to rank.

The ranking of general $i$ is a list with $i$ integers $p_{i,0},p_{i,1},\dots ,p_{i,i-1}$ in which every integer from $0$ to $i-1$ occurs exactly once. Specifically, $p_{i,0}$ is the best and $p_{i,i-1}$ is the worst general according to general $i$.

Output Specification

Print a list of integers, an ordering of the numbers $0,1,\dots ,N-1$, such that for each pair of adjacent numbers, neither is strictly in the second half of the other's ranking.

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

Constraints and Scoring

• $2\le N\le 1000$.
• $0\le p_{i,0},p_{i,1},\dots ,p_{i,i-1}\le i-1$ for $i=0,1,\dots ,N-1$.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Group	Score	Limits
1	11	The ranking of general $i$ will be $i-1,i-2,\dots ,0$ for all $i$ such that $1\le i\le N-1$.
2	23	The ranking of general $i$ will be $0,1,\dots ,i-1$ for all $i$ such that $1\le i\le N-1$.
3	29	$N\le 8$
4	37	No additional constraints.

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