Курс історії
Вам потрібно провести серію лекцій про важливі історичні події, по одній події на лекцію, у довільному порядку. Кожна подія охоплює певний часовий інтервал [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 лекцій. Не забудьте розташувати будь-які непов'язані інтервали в правильному порядку!