P6844 [CEOI 2019] Building Skyscrapers

On a 2D plane, there are $n$ grid cells where skyscrapers are planned to be built. The planned cell of the $i$-th skyscraper is located at $(r_i, c_i)$. You may choose any construction order of the skyscrapers, but it must satisfy the following rules: - Let the construction order be $s$. - For any $2 \le i \le n$, it must hold that skyscraper $s_i$ shares at least one common edge or a common corner with at least one previously built skyscraper. - For any $1 \le i \le n$, it must hold that from the planned cell of skyscraper $s_i$ to the boundary of the 2D plane, there exists a path (you can move from one cell only to a cell that shares a common edge with it), and on this path there are no other skyscrapers except $s_i$. An integer $t$ is also given, indicating the output type: - If $t = 1$, you need to construct any valid construction order. - If $t = 2$, you need to construct the construction order such that $(s_n, s_{n - 1}, \dots, s_1)$ is lexicographically largest.

The first line contains an integer $n$. The second line contains an integer $t$. The next $n$ lines each contain two integers $r_i, c_i$. Line $i$ indicates that the planned coordinates of the $i$-th skyscraper are $(r_i, c_i)$.

The first line outputs a string `YES` or `NO`, indicating whether a feasible solution exists. If a feasible solution exists, then output $n$ lines, each with one integer describing the order you construct. - If $t = 1$, you need to construct any valid construction order. - If $t = 2$, you need to construct the construction order such that $(s_n, s_{n - 1}, \dots, s_1)$ is lexicographically largest.

#### Sample Explanation #### Sample 1 Explanation These three skyscrapers form a line, so naturally there are the following solutions: - $1, 2, 3$ - $2, 1, 3$ - $2, 3, 1$ - $3, 2, 1$ Because $t = 2$, output the first one. #### Sample 2 Explanation The only difference from Sample 1 is that the three skyscrapers form a diagonal line. The solutions are the same as in Sample 1, and since $t = 1$, output any one solution. #### Sample 3 Explanation The two skyscrapers do not touch each other, so it is naturally impossible to build them. #### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 1.5 \times 10^5$, $1 \le t \le 2$, and $\lvert r_i \rvert, \lvert c_i \rvert \le 10^9$. The detailed subtask constraints and scores are shown in the table below: | Subtask ID | Constraints | Score | | :-: | :-: | :-: | | 1 | $t = 1$ and $n \le 10$ | $8$ | | 2 | $t = 1$ and $n \le 200$ | $14$ | | 3 | $t = 1$ and $n \le 2 \times 10^3$ | $12$ | | 4 | $t = 2$ and $n \le 2 \times 10^3$ | $17$ | | 5 | $t = 1$ | $20$ | | 6 | $t = 2$, $n \le 7 \times 10^4$, and $\lvert r_i \rvert, \lvert c_i \rvert \le 900$ | $10$ | | 7 | $t = 2$ | $19$ | #### Notes This problem is translated from [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 1](https://ceoi.sk/tasks/) [T1 Building Skyscrapers](https://ceoi.sk/static/statements/skyscrapers-ENG.pdf)。 Translated by ChatGPT 5