Курс історії#6772

Курс історії

30 секунд

256 мегабайтів

Складна

Вам потрібно провести серію лекцій про важливі історичні події, по одній події на лекцію, у довільному порядку. Кожна подія охоплює певний часовий інтервал $[a_{i}, b_{i}]$ [a_i, b_i]. Вважатимемо, що дві події пов'язані, якщо їхні інтервали перетинаються. Було б зручно організувати лекції по пов'язаних подіях так, щоб вони були близько одна до одної. Крім того, лекції по непов'язаних подіях повинні бути розташовані в хронологічному порядку (якщо подія $A$ передує непов'язаній з нею події $B$ , то лекція по $A$ повинна бути раніше, ніж лекція по $B$ ).

Знайдіть найменше ціле число $k \geq 0$ k \geq 0 і такий порядок лекцій, щоб будь-які дві пов'язані події знаходилися на відстані не більше $k$ лекцій одна від одної (лекції з номерами $i$ і $j$ знаходяться на відстані $∣ i - j ∣$ |i - j| одна від одної).

Вхідні дані

Перший рядок містить кількість тестів $t$ .

Структура кожного тесту наступна:

Перший рядок містить значення $n$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000).

Кожен з наступних $n$ рядків містить два цілі числа $a_{i}$ a_i і $b_{i}$ b_i ( $- 1 0^{9} \leq a_{i} \leq b_{i} \leq 1 0^{9}$ -10^9 \leq a_i \leq b_i \leq 10^9) — кінці $i$ -го інтервалу. Інтервали попарно різні.

Вихідні дані

Відповіді на тести виводьте в порядку їх слідування.

Перший рядок кожного тесту містить найменше значення $k$ .

Наступні $n$ рядків містять список інтервалів (у тому ж форматі, як і на вході) в такому порядку, щоб будь-які дві пов'язані події знаходилися на відстані не більше $k$ лекцій. Не забудьте розташувати будь-які непов'язані інтервали у правильному порядку!

Приклади

Приклад 1