P6844 [CEOI 2019] Building Skyscrapers

在 2D 平面上，有 $n$ 个计划建摩天楼的格子，第 $i$ 座计划建的摩天楼的格子位于 $(r_i,c_i)$。 您可以选择任意一种建摩天楼的顺序，但是要满足如下设定： - 设建摩天楼的顺序为 $s$。 - 对于任意 $2\le i\le n$，都要保证，第 $s_i$ 座至少和前面任意一座摩天楼有公共边或公共角。 - 对于任意 $1\le i\le n$，都要保证，从第 $s_i$ 座计划建摩天楼的格子到 2D 平面的边界，有路径相连（从一个格子只能走到与其有公共边的格子），且路径上除第 $s_i$ 座摩天楼无其他摩天楼。 同时会输入一个 $t$，表示输出的类别： - 若 $t=1$，您需要构造任意一种建造的顺序。 - 若 $t=2$，您需要构造 $(s_n, s_{n - 1}, \dots, s_1)$ 字典序最大的建造顺序。

第一行一个整数 $n$。 第二行一个整数 $t$。 接下来 $n$ 行，每行两个整数 $r_i,c_i$，第 $i$ 行表示第 $i$ 座计划建的摩天楼的坐标为 $(r_i,c_i)$。

第一行为一个字符串 `YES` 或者 `NO`，表示是否有一种可行的方案。 若有一种可行的方案，接下来输出 $n$ 行，一行一个整数表示您构造的方案。 - 若 $t=1$，您需要构造任意一种建造的顺序。 - 若 $t=2$，您需要构造 $(s_n, s_{n - 1}, \dots, s_1)$ 字典序最大的建造顺序。

#### 样例解释 #### 样例 1 解释 这是三个摩天楼连成一行，自然有如下几种解： - $1,2,3$ - $2,1,3$ - $2,3,1$ - $3,2,1$ 因为 $t=2$，所以输出第一种。 #### 样例 2 解释 和样例 1 的区别只是三个摩天楼连成一条对角线，与样例 1 的解一致，又因为 $t=1$，随便输出一组即可。 #### 样例 3 解释 两个摩天楼无相交部分，自然无法建立。 #### 数据范围 对于 $100\%$ 的数据，保证 $1\le n\le 1.5\times 10^5$，$1\le t\le 2$，$\lvert r_i \rvert,\lvert c_i \rvert\le 10^9$。 详细子任务限制及分值如下表： | 子任务编号 | 限制 | 分值 | | :-: |:-:|:-:| | 1 | $t=1$ 且 $n\le 10$ | $8$ | | 2 | $t=1$ 且 $n\le 200$ | $14$ | | 3 | $t=1$ 且 $n\le 2\times 10^3$ | $12$ | | 4 | $t=2$ 且 $n\le 2\times 10^3$ | $17$ | | 5 | $t=1$ | $20$ | | 6 | $t=2$，$n\le 7\times 10^4$ 且 $\lvert r_i \rvert,\lvert c_i \rvert\le 900$ | $10$ | | 7 | $t=2$ | $19$ | #### 说明 本题译自 [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)。