Domino sorting
Denis, a young programmer, received a set of dominoes as a birthday present. As Denis was a programmer he didn’t know how to play domino. That’s why he invented a new game: he took n dominoes from the set and made the rectangle 2 * n from them so that one domino piece makes one horizontal row. Then he swapped and turned over some of them in order to make numbers in the left column be sorted upside down in nondecreasing order and numbers in the right column 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 as Denis is a young programmer he got stuck with this problem. So he asked you to help him.
Input
First line contains an integer n (1 ≤ n ≤ 10^5). The following n lines describe dominoes. The i–th of these lines contains two integers a[i] and b[i] (0 ≤ a[i], b[i] ≤ 10^6). They correspond to numbers on the i-th domino.
Output
First line should contain YES if the given set of dominoes can be sorted as explained. Next n lines should describe the dominoes in the sorted order - two numbers separated by space in each line. Numbers in the first column should be nondecreasing and from the second column nonincreasing. If there is more than one solution you may output any of them. In case there is no solution you should a output single line NO.