Two-color coloring

Tony likes coloring books.

Tony first draws a picture using only circles and straight lines that join two circles. Not every pair of circles has a line between them. After drawing, he wants to color the circles so that two circles joined by a line get different colors.

Finding the smallest number of colors is hard, so Tony only wants to know whether two colors are enough.

You are given the numbers of the circles and the lines that join them. Decide whether the picture can be colored with two colors.

The first line contains the number of test cases $T$.

The first line of each test case contains the number of circles $n$ ($1 \le n \le 1000$) and the number of lines $m$ ($1 \le m \le 100000$). Each of the next $m$ lines describes one line of the picture as $x$ $y$, meaning that circle $x$ and circle $y$ are joined by a straight line. Circles are numbered from 1 to $n$. The same line may be given more than once.

For each test case print one line. Print possible if the picture can be colored with two colors, and impossible otherwise.