分数: 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