/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 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 は全て相異なることが保証されます。
あなたは (1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_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
P=(3,2,1,4) とすると、 N 回の操作は以下のように進みます。
- 1 回目：人 3 を座標 7 から座標 5 に移動させる。他の 3 人は座標 1,2,8 にいるため、喧嘩は発生しない。
- 2 回目：人 2 を座標 2 から座標 4 に移動させる。他の 3 人は座標 1,5,8 にいるため、喧嘩は発生しない。
- 3 回目：人 1 を座標 1 から座標 3 に移動させる。他の 3 人は座標 4,5,8 にいるため、喧嘩は発生しない。
- 4 回目：人 4 を座標 8 から座標 10 に移動させる。他の 3 人は座標 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
Score : 600 points
Problem Statement
There are N people on a number line.
Person i (1\le i\le N) is initially at coordinate S_i, and wants to eventually move to coordinate T_i. It is guaranteed that S_1,S_2,\ldots,S_N,T_1,T_2,\ldots,T_N are all distinct.
You fix one permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and perform N operations in order. In the i-th operation (1\le i\le N), you move person P_i from coordinate S_{P_i} to coordinate T_{P_i} along the shortest path on the number line. However, if there is another person on the movement path, a fight occurs.
Determine if there exists a P such that no fight occurs, and if it exists, find one.
Constraints
- 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 are all distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S_1 T_1 S_2 T_2 \vdots S_N T_N
Output
If there is no P such that no fight occurs, output No.
Otherwise, output a P such that no fight occurs in the following format.
Yes P_1 P_2 \ldots P_N
If there are multiple P that satisfy the condition, any of them will be accepted.
Sample Input 1
4 1 3 2 4 7 5 8 10
Sample Output 1
Yes 3 2 1 4
If P=(3,2,1,4), then the N operations proceed as follows.
- 1st operation: Move person 3 from coordinate 7 to coordinate 5. The other three people are at coordinates 1,2,8, so no fight occurs.
- 2nd operation: Move person 2 from coordinate 2 to coordinate 4. The other three people are at coordinates 1,5,8, so no fight occurs.
- 3rd operation: Move person 1 from coordinate 1 to coordinate 3. The other three people are at coordinates 4,5,8, so no fight occurs.
- 4th operation: Move person 4 from coordinate 8 to coordinate 10. The other three people are at coordinates 3,4,5, so no fight occurs.
Therefore, outputting P=(3,2,1,4) will be accepted.
Other acceptable outputs include P=(4,3,2,1),(2,1,3,4).
Sample Input 2
2 1 3 4 2
Sample Output 2
No
There is no P such that no fight occurs. Therefore, output No.
Sample Input 3
5 19 17 1 10 9 14 3 11 8 13
Sample Output 3
Yes 3 5 1 4 2