EduBrick

F. Объединение отрезков

2000 мс · 256 МБ · всё или ничего

Дано NN отрезков на числовой прямой. Некоторые из них пересекаются или касаются друг друга.

Представьте объединение всех отрезков в виде наименьшего числа отрезков и выведите их по возрастанию левого конца.

Формат ввода

В первой строке NN от 11 до 10510^5. В следующих NN строках — пары целых чисел LiL_i и RiR_i, причём LiRiL_i \le R_i и оба по модулю не больше 10910^9.

Формат вывода

В первой строке количество отрезков в объединении, далее сами отрезки, по одному в строке.

Примеры

ввод
4
0 2
4 5
1 3
5 6
вывод
2
0 3
4 6
Войдите, чтобы отправлять решения.