Даны 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