Кімнати матусі Два Черевички#13001

Кімнати матусі Два Черевички

У матусі Два Черевички є два бешкетні коти — Том і Бутч.

Вона має 2 \cdot n кімнат, розташованих уздовж прямого коридору, кожна з яких задається відрізком (l_i, r_i).

Матуся хоче виділити кожному коту окрему кімнату, але Том і Бутч не переносять один одного — якщо їхні кімнати перетинаються, бійки не уникнути! Щоб у домі панував мир, вона хоче розбити всі кімнати на пари так, щоб дві кімнати в кожній парі не перетиналися (вони можуть лише торкатися своїми межами).

Кожна кімната має входити рівно до однієї пари — жодна кімната не може належати двом різним парам.

Оскільки матуся любить мати вибір, вона хоче дізнатися, чи можливо утворити рівно таких пар без конфліктів.

Вхідні дані

Кожен тест складається з кількох наборів вхідних даних.

У першому рядку задано ціле число — кількість наборів вхідних даних.

Далі наведено опис кожного набору.

У першому рядку кожного набору задано ціле число — кількість пар, які матуся хоче утворити (тобто коридор містить 2 \cdot n кімнат).

У наступних 2 \cdot n рядках задано по два цілі числа l_i та r_i — кінці відрізка, що задає відповідну кімнату.

1 \le t, n \le 2 \cdot 10^5,

0 \le l_i < r_i \le 10^6,

сума всіх значень за всіма наборами вхідних даних не перевищує 2 \cdot 10^5.

Вихідні дані

Для кожного набору вхідних даних виведіть possible, якщо кімнати можна розбити на пари.

Інакше виведіть impossible.

Приклади

Приклад

Loading
Loading