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

1112. Покрытие

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Даны N отрезков на прямой. Каждый отрезок задан координатами своих концов Ai и Bi (Ai < Bi, 1 ≤ i ≤ N). Некоторые отрезки могут пересекаться. Напишите программу, которая уберёт минимальное количество отрезков из заданных, так что никакие два отрезка из оставшихся не будут иметь общей внутренней точки.

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

Первая строка ввода содержит целое число N (1 ≤ N ≤ 99). Каждая из следующих N строк содержит целые числа Ai и Bi (−999 ≤ Ai < Bi ≤ 999).

Результат

В первой строке выведите целое число P, равное количеству отрезков, которые остались после того, как ваша программа убрала лишние отрезки. Следующие P строк должны содержать координаты левых и правых концов оставленных отрезков. Координаты должны быть разделены одним пробелом. Отрезки должны быть выведены в порядке возрастания координат левых концов. Если задача имеет более одного решения, выведите любое из них.

Пример

исходные данныерезультат
3
3 6
1 3
2 5
2
1 3
3 6
Источник задачи: Bulgarian National Olympiad Day #2