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

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Domino Sorting

Time limit: 1.0 second
Memory limit: 64 MB
Problem illustration
Denis received a set of dominoes as a birthday present and soon he invented a new game: he takes n dominoes from the set and makes the rectangle from them so that one domino piece forms one horizontal row. The goal of the game is to swap and turn over some of the dominoes so that the numbers in the left column would be sorted upside down in nondecreasing order and numbers in the right column would be sorted in nonincreasing order. Denis called this game “domino sorting”.
However, this game takes a lot of time… Now Denis wants to write a program that will sort any suggested set of dominoes. But Denis is not a programmer yet, so he asked you to help him.


The first line contains an integer n (1 ≤ n ≤ 105). The i-th of the following n lines contains two space-separated integers ai and bi (0 ≤ ai, bi ≤ 106). They correspond to the numbers on the i-th domino.


Output “YES” if the given set of dominoes can be sorted as explained. Next n lines should describe the dominoes in the sorted order, two space-separated numbers in each line. Numbers in the first column should be nondecreasing and numbers in the second column should be nonincreasing. If there is more than one solution, you may output any of them. In case there is no solution, output “NO”.


5 2
6 1
3 4
1 6
2 5
3 4
1 5
7 1
3 8
5 6
1 7
1 5
6 5
8 3
1 2
3 4
Problem Author: Artyom Ripatti, Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
To submit the solution for this problem go to the Problem set: 1743. Domino Sorting