Arrange Carnival Managers

Every four years, the students of Lund gather to celebrate the Lund Carnival. During the festivities, the park is filled with tents and various celebrations, all coordinated by the carnival managers. There are \(N\) carnivals, and each carnival has a different manager. These managers are numbered \(0, 1, \dots, N-1\) in chronological order. For every manager \(i\) (\(i \ge 1\)), they provide a ranking of all previous managers \(0, 1, \dots, i-1\) from best to worst.

The managers will all appear in a group photo for the upcoming 2026 Carnival. However, if two managers \(i\) and \(j\) (with \(i < j\)) stand next to each other, and manager \(j\) ranked \(i\) in the strictly lower half of his/her list, then the situation will be awkward.

More formally, for any two adjacent managers \(i\) and \(j\) in the photo with \(i < j\):

• If \(j\) is even (i.e. the ranking list has \(j\) elements), then the allowed managers to stand beside \(j\) are those appearing in positions \(0, 1, \dots, \frac{j}{2}-1\) of \(j\)'s ranking (0-indexed).
• If \(j\) is odd, then the allowed managers are those in positions \(0, 1, \dots, \lfloor\frac{j}{2}\rfloor\) (i.e. the middle element is allowed, while the ones strictly after are not allowed).

Your task is to arrange all the managers \(0, 1, \dots, N-1\) in a line in such a way that whenever two managers \(i\) and \(j\) are adjacent with \(i < j\), the ranking of \(i\) in \(j\)'s list is not in the forbidden (strictly lower) half. If multiple valid arrangements exist, you may output any.

Note: The ranking list provided by manager \(j\) is a permutation of \(\{0, 1, \dots, j-1\}\).

inputFormat

The first line contains an integer \(N\) representing the number of carnivals (and managers). For every manager \(i\) from \(1\) to \(N-1\), the next line contains \(i\) integers. These integers denote the ranking of managers \(0, 1, \dots, i-1\) provided by manager \(i\) in order from best to worst.

For example, if \(N=4\), the input will be:

4
0
1 0
2 1 0

outputFormat

Output a permutation of \(0, 1, \dots, N-1\) (separated by spaces) that satisfies the constraint that for every adjacent pair \(i\) and \(j\) with \(i < j\), manager \(j\) does not have \(i\) in the forbidden half of his ranking list. If there are multiple valid arrangements, any one is acceptable.

sample

1

0