ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Сортировка домино

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
После того, как Денису на день рождения подарили набор домино, он придумал следующую игру. Денис берёт n костяшек домино из набора и составляет из них прямоугольник так, что в каждом горизонтальном ряду лежит ровно одна костяшка домино. Цель игры — поменять местами и перевернуть некоторые из костяшек таким образом, чтобы числа в левом столбце стали упорядочены по неубыванию, а в правом — по невозрастанию. Эту игру Денис назвал «сортировкой домино».
Но данная игра занимает много времени, поэтому Денис хочет написать программу, которая сама сортирует любой предложенный набор домино. Но Денис — ещё не программист, он только учится, поэтому он попросил об этом вас.

Исходные данные

В первой строке записано целое число n (1 ≤ n ≤ 105). В i-й из следующих n строк через пробел записаны два целых числа ai и bi (0 ≤ ai, bi ≤ 106). Они соответствуют числам на i-й костяшке домино.

Результат

Выведите «YES», если данный набор домино можно отсортировать указанным образом. В следующих n строках выведите домино в отсортированном порядке, по два числа в строке через пробел. Числа в первом столбце должны идти по неубыванию, а во втором — по невозрастанию. Если решений несколько, выведите любое из них. Если решения нет, выведите «NO».

Примеры

исходные данныерезультат
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
Автор задачи: Артём Рипатти, Пётр Лежанкин
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1743. Сортировка домино