#P1348F. Phoenix and Memory
Phoenix and Memory
No submission language available for this problem.
Description
Phoenix is trying to take a photo of his $n$ friends with labels $1, 2, \dots, n$ who are lined up in a row in a special order. But before he can take the photo, his friends get distracted by a duck and mess up their order.
Now, Phoenix must restore the order but he doesn't remember completely! He only remembers that the $i$-th friend from the left had a label between $a_i$ and $b_i$ inclusive. Does there exist a unique way to order his friends based of his memory?
The first line contains one integer $n$ ($1 \le n \le 2\cdot10^5$) — the number of friends.
The $i$-th of the next $n$ lines contain two integers $a_i$ and $b_i$ ($1 \le a_i \le b_i \le n$) — Phoenix's memory of the $i$-th position from the left.
It is guaranteed that Phoenix's memory is valid so there is at least one valid ordering.
If Phoenix can reorder his friends in a unique order, print YES followed by $n$ integers — the $i$-th integer should be the label of the $i$-th friend from the left.
Otherwise, print NO. Then, print any two distinct valid orderings on the following two lines. If are multiple solutions, print any.
Input
The first line contains one integer $n$ ($1 \le n \le 2\cdot10^5$) — the number of friends.
The $i$-th of the next $n$ lines contain two integers $a_i$ and $b_i$ ($1 \le a_i \le b_i \le n$) — Phoenix's memory of the $i$-th position from the left.
It is guaranteed that Phoenix's memory is valid so there is at least one valid ordering.
Output
If Phoenix can reorder his friends in a unique order, print YES followed by $n$ integers — the $i$-th integer should be the label of the $i$-th friend from the left.
Otherwise, print NO. Then, print any two distinct valid orderings on the following two lines. If are multiple solutions, print any.
Samples
4
4 4
1 3
2 4
3 4
YES
4 1 2 3
4
1 3
2 4
3 4
2 3
NO
1 3 4 2
1 2 4 3