만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

색칠하기

시간 제한2초메모리 제한256 MB

요약
무방향 다중 그래프가 주어질 때, 두 가지 색으로 칠할 수 있는지, 즉 이분 그래프인지 판별한다.
난이도

쉬움10점 중 3점

유형
그래프, BFS, DFS
정답자
아직 제출이 없습니다

문제

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

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

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

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

입력

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

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

출력

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

예제3

  1. 예제 1

    입력
    3
4 5
1 2
2 3
3 4
1 3
2 4
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
8 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
    예상 출력
    impossible
possible
possible

  2. 예제 2

    입력
    1
2 1
1 2
    예상 출력
    possible

  3. 예제 3

    입력
    1
3 3
1 2
2 3
3 1
    예상 출력
    impossible