League of Overwatch at Moloco (Hard)

Time limit2sMemory limit512 MB

Summary

Given n employees and m conflict pairs, decide whether the employees can be split into two non-empty groups so that no pair shares a group.

Level: Medium4 of 10
Topics: Graph, DFS, Union-find
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

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

Examples2

Example 1
Input
```
3 4
1 2
2 3
3 1
2 1
```
Expected output
```
IMPOSSIBLE
```
Example 2
Input
```
3 3
1 2
1 2
2 3
```
Expected output
```
POSSIBLE
```