题目描述

在 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)$ 字典序最大的建造顺序。

3
2
0 0
0 1
0 2

YES
1
2
3

3
1
0 0
1 1
2 2

YES
2
3
1

2
1
0 0
0 2

NO

提示

样例解释

样例 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 Day 1 T1 Building Skyscrapers。