DSU
Переворот карт
Майк и его юная дочь Джесси играют в новую карточную игру, предназначенную для детей. Правила довольно просты, каждый игрок получает набор карт. Каждая карта имеет одну картинку на каждой стороне. Они ходят по очереди, и первый кто избавится от игральных карт, является победителем.
Ход игрока состоит в выборе некоторого подмножества имеющегося у него карт и выкладки их на стол. Но имеется одно правило: карты должны быть размещены на столе так, чтобы никакие две из них не показывали одну и ту же картинку.
Майк подумал, что было бы очень уместно сыграть со своим ребенком из-за простых правил. Майк также полюбил эту игру, потому что нахождение наилучшей стратегии является алгоритмически интересной задачей!
Помогите Майку определить, сможет ли он выложить все карты на стол за один ход.
Giriş verilənləri
Первая строка содержит количество тестов t\:(t \le 10). Каждый тест начинается количеством карт n\:(1 \le n \le 50000) на руках у Майка. Следующие n строк описывают сами карты имеющиеся у Майка.
Картинки на картах представлены числами. i-ая карта задается двумя числами p_i, q_i где 1 \le p_i, q_i \le 2n.
Çıxış verilənləri
Для каждого теста вывести в отдельной строке слово possible если Майк сможет выложить на стол все карты за один ход, и impossible если не сможет.
Nümunə
3 3 1 2 1 3 2 3 3 1 2 1 2 1 2 1 1 1
possible impossible possible