Flipping Cards#7538
Mike and his young daughter Jessie are playing a new card game designed for children. The rules are quite simple: each player receives a set of cards. Each card has one picture on each side. The players take turns, and the one who gets rid of all their cards first wins.
On a player's turn, they choose some subset of the cards they have and place them on the table. However, there is one rule: the cards must be placed so that no two of them show the same picture.
Mike thought that this game would be perfect to play with his child due to its simplicity. Moreover, he liked it because finding the optimal strategy is an algorithmically interesting problem!
Help Mike determine whether he can place all his cards on the table in a single move.
The first line contains the number of test cases t~(t \le 10). Each test case begins with an integer n~(1 \le n \le 50000) — the number of cards Mike has. The following lines describe the cards.
The pictures on the cards are represented by integers. The -th card is described by two integers p_i, q_i, where 1 \le p_i, q_i \le 2n.
For each test case, print one line containing the word possible if Mike can place all the cards on the table in one move, or impossible otherwise.
Example 1