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 \leq N \leq 1\,000~.
• ~0 \leq p_{i,0}, p_{i,1}, \dots, p_{i,i-1} \leq 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.

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

---