P6676 [COCI 2019/2020 #2] Slagalica

## 本题征集 SPJ。但若您写的是正解，即，输出了字典序最小解，仍可获得 AC 的评测结果。 小斌喜欢玩拼图。

This problem is collecting an SPJ. However, if you submit the correct solution, i.e., output the lexicographically smallest solution, you can still get AC. Xiao Bin likes playing jigsaw puzzles. Xiao Bin got a one-dimensional jigsaw puzzle game consisting of $n$ pieces. He soon realized that each piece belongs to one of the following types:  Also, among these $n$ pieces, there is exactly one type $5$ or type $6$ piece (the left border), and exactly one type $7$ or type $8$ piece (the right border). Xiao Bin wants to arrange all pieces into a single row such that the first (leftmost) piece is of type $5$ or type $6$, and the last (rightmost) piece is of type $7$ or type $8$. Two pieces can be placed next to each other if and only if the shapes of their adjacent borders are different, i.e., one border is concave and the other border is convex. This is too easy for Xiao Bin, so he decided to write a unique positive integer on each piece. Now he wants to find the lexicographically smallest arrangement. Note: Pieces cannot be rotated.

The input has $n + 1$ lines. The first line contains a positive integer $n$. Each of the next $n$ lines contains two integers $x_i$ and $a_i$. Here, $x_i$ denotes the type of the piece, and $a_i$ is the number Fabian wrote on it. The input guarantees that all $a_i$ are distinct.

Output one line. If Xiao Bin cannot solve the puzzle, output `-1`. Otherwise, output the lexicographically smallest sequence of numbers on the pieces.

#### Sample #1 Explanation There are only $2$ solutions, as shown below:  You can see that the second solution is lexicographically smaller, so the output is `1 3 7 5 4`. #### Constraints For $100\%$ of the testdata, $2 \le n \le 10^5$, $1 \le x_i \le 8$, and $1 \le a_i \le 10^9$. If you do not output the lexicographically smallest solution and only construct any valid solution, you can get $40\%$ of the score. #### Notes **The score of this problem follows the original COCI setting, with a full score of $70$.** **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T2 Slagalica*.** Translated by ChatGPT 5