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