색칠하기

토니킴은 색칠공부를 좋아한다.

토니킴은 먼저 동그라미 여러 개와 동그라미 두 개를 잇는 직선만으로 그림을 그린다. 모든 동그라미 쌍 사이에 직선이 있어야 하는 것은 아니다. 그림을 그린 다음에는 직선으로 이어진 두 동그라미의 색이 서로 다르도록 색을 칠하려고 한다.

필요한 색의 최소 개수를 구하는 것은 어렵기 때문에, 토니킴은 색 두 가지로 칠할 수 있는지만 알고 싶어한다.

동그라미의 번호와 동그라미를 잇는 직선의 정보가 주어진다. 이 그림을 색 두 가지로 칠할 수 있는지 판정하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 동그라미의 개수 $n$ ($1 \le n \le 1000$)과 직선의 개수 $m$ ($1 \le m \le 100000$)이 주어진다. 이어지는 $m$개의 줄에는 직선 하나의 정보가 $x$ $y$ 형식으로 주어지며, 동그라미 $x$와 동그라미 $y$가 직선으로 이어져 있다는 뜻이다. 동그라미의 번호는 1부터 $n$까지이다. 같은 직선이 두 번 이상 주어질 수 있다.

각 테스트 케이스마다 한 줄을 출력한다. 색 두 가지로 칠할 수 있으면 possible을, 칠할 수 없으면 impossible을 출력한다.