몰로코의 리그 오브 오버워치 (Hard)

몰로코 직원들은 가끔 두 그룹으로 나뉘어 리그 오브 오버워치 5판 3선승제 대결을 벌인다. 직원 중에는 예전에 듀오를 맺고 함께 플레이한 열성 게이머 쌍이 있는데, 회사는 이런 쌍을 서로 다른 그룹에 넣기로 했다. 경쟁이 과열되지 않아야 초보자도 행사를 즐길 수 있기 때문이다.

몰로코에는 직원이 $n$명 있고, 1번부터 $n$번까지 번호가 붙어 있다.

예전에 듀오로 함께 플레이한 직원 쌍 $(f_i, s_i)$가 $m$개 알려져 있다. 한 쌍의 두 직원은 이번 행사에서 서로 다른 그룹에 속해야 한다.

직원 $n$명을 비어 있지 않은 두 그룹으로 나눌 수 있는지 판정하라. 각 직원은 정확히 한 그룹에만 속하고, 어떤 쌍 $(f_i, s_i)$도 두 직원이 같은 그룹에 들어가면 안 된다.

첫째 줄에 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($1 \le n \le 1\,000\,000$, $1 \le m \le 1\,000\,000$)

다음 $m$개 줄 중 $i$번째 줄에는 정수 $f_i$와 $s_i$가 주어진다. ($1 \le f_i, s_i \le n$) 모든 $i$에 대해 $f_i \ne s_i$가 보장된다. 같은 쌍이 여러 번 주어지기도 한다.

조건을 만족하는 분할이 존재하면 POSSIBLE을, 존재하지 않으면 IMPOSSIBLE을 한 줄에 출력한다.

두 번째 예제에서는 {2}와 {1, 3}으로 나누면 조건을 만족한다.