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

1743. 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.

Input

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

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”.

Samples

inputoutput
3
5 2
6 1
3 4
YES
1 6
2 5
3 4
4
1 5
7 1
3 8
5 6
YES
1 7
1 5
6 5
8 3
2
1 2
3 4
NO
Problem Author: Artyom Ripatti, Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009