题目描述

有一个无限大的二维网格图，我们计划在网格图上建造 $n$ 座塔，第 $i$ 座塔的所在格子的坐标为 $(a_i,b_i)$。接下来我们将尝试着规划出一种建造的顺序依次建塔。不妨设我们建塔的顺序为长度为 $n$ 的排列 $p_1,p_2,\ldots,p_n$，由于一些特殊的原因，建塔顺序 $p$ 需要满足一些特定的条件。

首先，由于政府需要让人们确信建塔的工程是有组织有计划的，政府需要确保自己的建塔的过程显得很有规划。具体来说，建造的第一座塔可以是任何一座塔，但是对于之后建造的所有塔，例如在建造第 $i$ 座塔（$2\le i\le n$）时，需要确保该塔与前 $i-1$ 座已经建造的塔有着一定的联系。进一步的，我们要求前 $i-1$ 座塔中存在至少一座塔与该塔在网格图中有公共边或公共点，这一要求对第一座之后建造的所有塔均有效。

其次，尽管网格图内幅员辽阔、物资充沛，但在建造一座塔时，若该塔被四周的若干塔包围，则建造工作仍然会受到极大影响（外围边界的物资受到其他塔的阻隔无法运输进来）。为了保证计划的正常进行，我们要求当正在建造第 $i$ 座塔时，确保第 $i$ 座塔所在的格子满足：以该塔作为起点，之后可以移动到有公共边的相邻空格子（要求移动到的目标格子上没有已经完成建造的塔），并通过这种公共边移动的方式可以移动到网格的无限远处（显然无限远处是互相连通的）。

最后，出于各种原因，人们会对新建造的塔显得更加记忆深刻，越新建造的塔如果编号越大，则越对人们有着吸引力。因此政府可能希望我们规划出的顺序排列 $p$ 满足 $\{p_n,p_{n-1},p_{n-2},\ldots,p_1\}$ 的字典序最大化。当然，这在一定程度上取决于政府对此事的关心程度，因此有时我们对此不做要求，规划任意一种合法顺序即可。

输入格式

输入的第一行包含一个整数 $n$，表示网格中计划建造的塔的数量。

输入的第二行包含一个整数 $\mathrm{type}$，表示规划类型：

• 若 $\mathrm{type}=1$，则构造任意一组合法顺序；
• 若 $\mathrm{type}=2$，则构造满足 $\{p_n,p_{n-1},p_{n-2},\ldots,p_1\}$ 字典序最大的合法顺序。

接下来 $n$ 行，每行两个整数 $a_i,b_i$，表示第 $i$ 座塔在网格图中的所在坐标 $(a_i,b_i)$。

输出格式

输出的第一行一个字符串。若不存在合法顺序，则输出 NO，结束；否则输出 YES，继续构造。

接下来输出包含 $n$ 行，第 $i$ 行表示在计划中建造的第 $i$ 座塔在输入中的编号。评测将根据 $\mathrm{type}$ 类型进行评分。

样例

输入

5
1
0 0
-1 -1
-1 1
1 -1
1 1

输出

YES
1
2
3
4
5

数据范围

本题开启子任务评测。

对于所有数据，保证

$$1\le n\le 1.5\times 10^5,\qquad \mathrm{type}\in\{1,2\}, \qquad -10^9\le a_i,b_i\le 10^9.$$

子任务编号	$n\le$	$\mathrm{type}=$	特殊性质	子任务分值
1	$10$	$1$		10
2	$200$			20
3	$2\times 10^3$			10
4		$2$
5	$1.5\times 10^5$	$1$		15
6	$7\times 10^4$	$2$	A
7	$1.5\times 10^5$			20

特殊性质 A：保证

$$-10^3\le a_i,b_i\le 10^3.$$