题目描述

译自 CEOI 2019 Day1 T1「Building Skyscrapers」

我们正计划建造一个占地非常大的正方形新城市：M 市。建造完成后，这个城市将会有 $n$ 座互不重叠的摩天楼，每个占据正方形网格中的一格。在任意时刻，没有摩天楼的格子被称作空格子。

你现在知道了这 $n$ 座计划中的摩天楼的坐标，你的任务是找出一个能满足下列要求的建造顺序：

• 因为建造组只有一台起重机，所以 M 市一次只能建一座摩天楼；
• 第一座摩天楼的建造位置没有限制；
• 为了更方便地布局摩天楼，除第一座摩天楼外，即将新建的摩天楼要与现有的摩天楼有至少一条公共边或一个公共角；
• 为了方便运输材料，即将新建的摩天楼必须与 M 市的边界（对于坐标 $(r,c)$ ，有$|r|,|c|>10^9$）有路径相连（从一个格子只能走到与其有公共边的格子），且路径上除即将新建的摩天楼外不能有摩天楼。

如果有解，假设建设顺序是 $s_1,\ldots ,s_n$，本题有两种模式：

• 模式一：你可以以任意顺序输出；
• 模式二：你必须保证 $(s_n,s_{n-1},\ldots ,s_1)$ 字典序最大，即在保证 $s_n$ 最大的情况下保证 $s_{n-1}$ 最大，以此类推。

输入格式

第一行一个整数 $n$，表示摩天楼个数。

第二行一个整数 $t$，表示这个子任务的模式。

接下来 $n$ 行每行两个以空格分隔的整数 $r_i,c_i$，表示摩天楼 $i$ 的坐标。

输入数据保证摩天楼不重叠。

输出格式

如果无解，输出 NO。
如果有解，输出 $n+1$ 行。第一行输出 YES，接下来 $n$ 行每行一个整数表示 $s_i$。
对于 $t=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\le n\le 1.5\times 10^5,t\in\{1,2\},|r_i|,|c_i|\le 10^9$。

详细子任务附加限制如下表：