League of Overwatch at Moloco (Easy)

Interview

Time limit2sMemory limit512 MB

Summary

Given a conflict graph, decide whether the vertices can be split into two non-empty groups so every conflicting pair is separated.

Level: Easy3 of 10
Topics: Graph, BFS
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 have already played together as a duo, so the company separates each such pair for this event to keep it enjoyable for beginners.

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

There are $m$ known pairs $(f_i, s_i)$ : employees $f_i$ and $s_i$ played a duo game in the past, so they must end up in different groups.

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 members in the same group.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 16$ , $1 \le m \le 150$ ).

Each 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 can appear more than once.

Output

Print one line containing either POSSIBLE or IMPOSSIBLE.

Hint

In the second example, splitting the employees into $\{2\}$ and $\{1, 3\}$ satisfies every constraint.

Examples3

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
```
Example 3
Input
```
2 1
1 2
```
Expected output
```
POSSIBLE
```