e-olymp
Змагання

Spanning Tree + DSU

Переворот карт

Майк и его юная дочь Джесси играют в новую карточную игру, предназначенную для детей. Правила довольно просты, каждый игрок получает набор карт. Каждая карта имеет одну картинку на каждой стороне. Они ходят по очереди, и первый кто избавится от игральных карт, является победителем.

Ход игрока состоит в выборе некоторого подмножества имеющегося у него карт и выкладки их на стол. Но имеется одно правило: карты должны быть размещены на столе так, чтобы никакие две из них не показывали одну и ту же картинку.

Майк подумал, что было бы очень уместно сыграть со своим ребенком из-за простых правил. Майк также полюбил эту игру, потому что нахождение наилучшей стратегии является алгоритмически интересной задачей!

Помогите Майку определить, сможет ли он выложить все карты на стол за один ход.

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

Первая строка содержит количество тестов t (t10). Каждый тест начинается количеством карт n (1n50 000) на руках у Майка. Следующие n строк описывают сами карты имеющиеся у Майка.

Картинки на картах представлены числами. i-ая карта задается двумя числами pi, qi где 1pi, qi2n.

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

Для каждого теста вывести в отдельной строке слово possible если Майк сможет выложить на стол все карты за один ход, и impossible если не сможет.

Ліміт часу 2 секунда
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
3
3
1 2
1 3
2 3
3
1 2
1 2
1 2
1
1 1
Вихідні дані #1
possible
impossible
possible
Джерело 2015 ACM North America - Rocky Mountain, Problem B