Сортування доміно#8435

Сортування доміно

1 секунда

128 мегабайтів

Легка

Денис, молодий програміст, отримав набір доміно як подарунок на день народження. Оскільки він не знав, як грати в доміно, то вигадав нову гру: він взяв $n$ доміно з набору і розмістив їх у прямокутник розміром $2 \times n$ 2 \times n, так що кожна доміношка утворює один горизонтальний рядок. Потім він переставляв і перевертав деякі з них так, щоб числа в лівому стовпці були відсортовані зверху вниз у неубувному порядку, а числа в правому стовпці — у невзростаючому порядку. Денис назвав цю гру сортування доміно.

Однак ця гра займає багато часу... Тепер Денис хоче написати програму, яка буде сортувати будь-який запропонований йому набір доміно. Але оскільки Денис молодий програміст, він просить вас допомогти йому.

Вхідні дані

Перша строка містить ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5). Наступні $n$ строк описують доміно. $i$ -ий рядок містить два цілі числа $a_{i}$ a_i і $b_{i}$ b_i ( $0 \leq a_{i}, b_{i} \leq 1 0^{6}$ 0 \le a_i, b_i \le 10^6). Вони відповідають числам на $i$ -му доміно.

Вихідні дані

У першому рядку виведіть YES, якщо заданий набір доміно можна відсортувати, як описано. Наступні $n$ рядків повинні описувати доміно у відсортованому вигляді — по два числа в кожному рядку. Числа в першій колонці повинні йти у неубувному порядку, а в другій колонці — у невзростаючому порядку. Якщо існує декілька рішень, виведіть будь-яке. Якщо рішення не існує, виведіть у першому рядку NO.

Приклади

Приклад 1

Приклад 2

Приклад 3