← 返回题目列表

AtCoder · arc205_c

C. 无碰撞移动

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 数轴上的人。

人 i (1\le i\le N) 最初位于坐标处 S_i,并希望最终移动到坐标 T_i。可以保证 S_1,S_2,\ldots,S_N,T_1,T_2,\ldots,T_N 都是不同的。

您修复了一种排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 并执行 N 操作按顺序进行。在 i第次操作 (1\le i\le N),你移动人 P_i 来自坐标 S_{P_i} 协调 T_{P_i} 沿着数轴上的最短路径。然而,如果移动路径上有另一个人,就会发生战斗。

判断是否存在 P 这样就不会发生战斗,如果存在,则找到一个。

约束

  • 1\le N\le 2\times 10^5
  • 1\le S_i, T_i \le 10^9
  • S_1,S_2,\ldots,S_N,T_1,T_2,\ldots,T_N 都是不同的。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
S_1 T_1
S_2 T_2
\vdots
S_N T_N

输出

如果没有 P 这样就不会发生战斗,输出 No.

否则,输出 P 这样在以下格式中不会发生战斗。

Yes
P_1 P_2 \ldots P_N

如果有多个 P 满足条件,其中任何一个都将被接受。


示例输入 1

4
1 3
2 4
7 5
8 10

示例输出 1

Yes
3 2 1 4

If P=(3,2,1,4),那么 N 操作进行如下。

  • 1st操作:移动人员 3 来自坐标 7 协调 5。另外三人在坐标处 1,2,8,所以不会发生战斗。
  • 2nd操作:移动人物 2 来自坐标 2 协调 4。另外三人在坐标处 1,5,8,所以不会发生战斗。
  • 3rd操作:移动人员 1 来自坐标 1 协调 3。另外三人在坐标处 4,5,8,所以不会发生战斗。
  • 4第次操作:移动人员 4 来自坐标 8 协调 10。另外三人在坐标处 3,4,5,所以不会发生战斗。

因此,输出 P=(3,2,1,4) 将被接受。

其他可接受的输出包括 P=(4,3,2,1),(2,1,3,4).


示例输入 2

2
1 3
4 2

示例输出 2

No

没有 P 这样就不会发生战斗。因此,输出 No.


示例输入 3

5
19 17
1 10
9 14
3 11
8 13

示例输出 3

Yes
3 5 1 4 2