League of Overwatch at Moloco (Hard)

Every so often the employees of Moloco split into two groups and play a best-of-five series of League of Overwatch. Some pairs of employees are hardcore gamers who queued together as a duo in the past, so the company puts every such pair on opposite sides. The event stays enjoyable for newcomers only when it is not that competitive.

Moloco has $n$ employees, numbered 1 through $n$.

There are $m$ known pairs $(f_i, s_i)$ of employees who played a duo game together in the past. The two employees of a pair must belong to different groups at this event.

Decide whether the $n$ employees can be split into two non-empty groups so that every employee belongs to exactly one group and no pair $(f_i, s_i)$ has both of its employees in the same group.

The first line contains two integers $n$ and $m$ separated by a space ($1 \le n \le 1\,000\,000$, $1 \le m \le 1\,000\,000$).

The $i$-th of the next $m$ lines contains two integers $f_i$ and $s_i$ ($1 \le f_i, s_i \le n$). It is guaranteed that $f_i \ne s_i$ for every $i$. The same pair is given more than once in some inputs.

Print one line containing POSSIBLE if such a split exists, and IMPOSSIBLE otherwise.

In the second example, the split {2} and {1, 3} satisfies every condition.