eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Курс истории

Курс истории

Лимит времени 30 секунд
Лимит использования памяти 256 MiB

Вам предстоит дать серию лекций о важных исторических событиях, по одному событию за лекцию в произвольном порядке. Каждое событие длилось некоторый временной интервал [a_i, b_i]. Будем говорить, что два события связаны между собой, если их интервалы имеют общую точку. Было бы удобно планировать лекции по связанным событиям близко друг к другу. Более того, лекции по несвязанным событиям должны планироваться в их хронологическом порядке (если событие A предшествует несвязанному с ним событию B, то лекция по A должна предшествовать лекции по B).

Найдите наименьшее целое k 0 и такой порядок лекций, что любые два связанных события находятся на расстоянии не более k лекций друг от друга (лекции с номерами i и j находятся на расстоянии |i - j| друг от друга).

Входные данные

Первая строка содержит количество тестов t. Структура каждого теста следующая:

Первая строка содержит значение n (1 n 50000). Каждая из следующих n строк содержит два целых числа a_i и b_i (-10^9a_ib_i10^9) - концы i-го интервала. Интервалы попарно различны.

Выходные данные

Ответы на тесты выводить в порядке их следования. Первая строка каждого теста содержит наименьшее значение k. Следующие n строк содержат список интервалов (в том же формате как и на входе) в таком порядке, что любые два связанных события находятся на расстоянии не более k лекций. Не забудьте расположить любые несвязанные интервалы в правильном порядке!

Пример

Входные данные #1
1
3
1 6
2 3
4 5
Выходные данные #1
1
Источник 2013 ACM ICPC Central Europe Regional Contest, Краков, Ноябрь 15-17, Задача G