ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Nanomatryoshkas

Time limit: 1.0 second
Memory limit: 64 MB
Matryoshka is a traditional Russian recursive doll. But everything changes, and even matryoshka needs a little innovation. Due to the use of new materials, it became possible to make a matryoshka arbitrarily thin without decreasing its durability. Soon, these new nanomatryoshkas filled the market. Now, salesman Alexander has a problem: he needs to place all nanomatryoshkas on a shelf in his shop.
Each nanomatryoshka has an internal volume and an external volume. One nanomatryoshka fits into another if the external volume of the first one does not exceed the internal volume of the second one. Alexander is sure that nanomatryoshkas should be placed in a row so that no nanomatryoshka (except the last one) fits into the next one in the row. Help Alexander, and he might give you a discount for a couple of nanomatryoshkas!


The first line contains an integer n (2 ≤ n ≤ 105) which is the number of nanomatryoshkas. Next n lines contain two integers each: internal and external volumes of a corresponding nanomatryoshka. It is guaranteed that the internal volume of each nanomatryoshka never exceeds the external volume, but they can be equal. Both numbers are in range from 1 to 106.


If it is impossible to place nanomatryoshkas in the described order, print “No”. Otherwise, on the first line, print “Yes”, and on the second line, print n integers: the numbers of nanomatryoshkas in their order on the shelf. Nanomatryoshkas are numbered starting from one in the order of their appearance in the input file. If there are several solutions, print any of them.


1 5
2 2
6 7
3 1 2 
2 2
2 2
3 4
Problem Author: Oleg Merkurev
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014
To submit the solution for this problem go to the Problem set: 2041. Nanomatryoshkas