Two-color coloring

Time limit2sMemory limit256 MB

Summary

Given an undirected multigraph, decide whether it is bipartite so its vertices can be colored with two colors.

Level: Easy3 of 10
Topics: Graph, BFS, DFS
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1

Input

Expected output

impossible
possible
possible

Example 2
Input
```
1
2 1
1 2
```
Expected output
```
possible
```
Example 3
Input
```
1
3 3
1 2
2 3
3 1
```
Expected output
```
impossible
```