Курс истории
Вам предстоит дать серию лекций о важных исторических событиях, по одному событию за лекцию в произвольном порядке. Каждое событие длилось некоторый временной интервал [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^9 ≤ a_i ≤ b_i ≤ 10^9) - концы i-го интервала. Интервалы попарно различны.
Выходные данные
Ответы на тесты выводить в порядке их следования. Первая строка каждого теста содержит наименьшее значение k. Следующие n строк содержат список интервалов (в том же формате как и на входе) в таком порядке, что любые два связанных события находятся на расстоянии не более k лекций. Не забудьте расположить любые несвязанные интервалы в правильном порядке!