Problem B
Flipping Cards

A player’s turn consists of picking a subset of cards from their hand and laying them on the table. The only rule is that the cards must be placed on the table such that no two cards are showing the same picture.

Mike thought this was a very appropriate game to play with his kid because of the simple rules. Mike also liked this game because finding the best strategy is an algorithmically interesting challenge!

Help Mike determine if he can play his entire hand on his first round.

Input

The first line of the input contains a single positive integer $T$ ($T \leq 10$) indicating the number of test cases. Each test case begins with a single integer $n$ denoting the number of cards in Mike’s hand. Here $1 \leq n \leq 50\, 000$. Following this are $n$ lines, each describing a card in Mike’s hand.

The pictures on the cards are represented by integers. The $i$th card is given by two integers $p_ i, q_ i$ where $1 \leq p_ i, q_ i \leq 2n$.

Output

For each test case you should output a single line with the word possible if it is possible for Mike to play his entire hand in one turn, or impossible if Mike cannot play his entire hand in one turn.

3
3
1 2
1 3
2 3
3
1 2
1 2
1 2
1
1 1

possible
impossible
possible