我们将建造一座新城市:大都会。这座城市将建立在一个无限的方形网格上。完成的城市将由 $$$n$$$ 摩天大楼组成,每座摩天大楼占据网格的不同单元。在施工过程中的任何时刻,当前不包含摩天大楼的单元格都被称为空单元格。
您将获得 $$$n$$$ 摩天大楼的计划坐标。您的任务是找到构建它们的顺序,同时满足下面列出的规则。
- 建筑人员只有一台起重机,因此大都市必须一次建造一座摩天大楼。
- 第一座摩天大楼可以建造在网格上的任何地方。
- 每个后续摩天大楼都必须与至少一个先前建造的摩天大楼共享一侧或角落(以便更容易将新摩天大楼正确对齐到网格)。
- 建造摩天大楼时,必须有一种方法可以将材料从大都会外部运送到建筑工地,只需将其移动到共享一侧的空单元格即可。换句话说,应该有一条侧面相邻的空单元格路径,将包含摩天大楼的单元格连接到某个单元格 $$$(r,c)$$$,其中 $$$|r|>10^9$$$ 和/或 $$$|c|>10^9$$$。
如果存在解决方案,让我们按照摩天大楼的建造顺序来表示摩天大楼的数量 $$$s_1, \dots, s_n$$$。子任务有两种类型:
类型 1:您可以出示任何有效订单。
类型 2:您必须找到最大化 $$$s_n$$$ 的顺序。其中,您必须找到最大化 $$$s_{n-1}$$$ 的那个。等等。换句话说,您必须找到有效的构建顺序,其中序列 $$$(s_n,s_{n-1},\dots,s_1)$$$ 按字典顺序最大。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 150,000$$$) – 摩天大楼的数量。
第二行包含一个整数 $$$t$$$ ($$$1 \le t \le 2$$$) 描述上面定义的子任务的类型。
然后是 $$$n$$$ 行。这些行的第 $$$i$$$ 包含两个空格分隔的整数 $$$r_i$$$ 和 $$$c_i$$$ ($$$|r_i|, |c_i| \le 10^9$$$),表示包含摩天大楼 $$$i$$$ 的单元格的坐标。
(摩天大楼没有按任何特定顺序编号。它们具有编号的唯一原因是它们在输出格式中使用。)
保证没有两座摩天大楼重合。
输出
如果不可能根据给定的规则建造摩天大楼,则打印包含字符串“NO”的单行。
否则,打印 $$$n+1$$$ 行。这些行的第一行应包含字符串“YES”。对于每个 $$$i$$$,剩余 $$$n$$$ 行中的第 $$$i$$$ 行应包含单个整数 $$$s_i$$$。
在$$$t = 1$$$的子任务中,如果有多个有效订单,则可以输出其中任何一个。
示例
输入 #1
3 2 0 0 0 1 0 2
输出 #1
YES 1 2 3
输入 #2
3 1 0 0 1 1 2 2
输出 #2
YES 2 3 1
输入 #3
2 1 0 0 0 2
输出 #3
NO
注意
评分:
子任务 1(8 分):$$$t = 1$$$ 和 $$$n \le 10$$$
子任务 2(14 分):$$$t = 1$$$ 和 $$$n \le 200$$$
子任务 3(12 分):$$$t = 1$$$ 和 $$$n \le 2,000$$$
子任务 4(17 分):$$$t = 2$$$ 和 $$$n \le 2,000$$$
子任务 5(20 分):$$$t = 1$$$
子任务 6(10 分):$$$t = 2$$$、$$$n \le 70,000$$$ 和 $$$|r_i|、|c_i| \le 900$$$ 每 $$$i$$$
子任务 7(19 分):$$$t = 2$$$
在第一个示例中,有三座摩天大楼排成一排。所有这些都可以从大都会外部到达,并且有四种构建顺序可以保持连接:
- 1, 2, 3
- 2, 1, 3
- 2, 3, 1
- 3, 2, 1
由于$$$t = 2$$$,我们必须选择第一个选项。
在第二个示例中,与第一个示例的唯一区别是摩天大楼 2 仅与摩天大楼 1 和 3 共享角点,与第一个示例中相同的订单集有效。由于 $$$t = 1$$$,因此这些答案都是正确的。
在第三个示例中,Metropolis 已断开连接。我们显然无法构建它。