Ride Placement Feasibility

You are given a set of plot areas represented by n nodes and m paths connecting some pairs of these plots. Each path connects two distinct plots. Your task is to determine whether it is possible to place the rides on some of these plots so that no two adjacent plots (i.e. plots connected by a path) both have a ride installed.

This problem can be reduced to checking whether the given graph is bipartite. In other words, you need to decide if the vertices of the graph can be colored with two colors such that no two adjacent vertices share the same color. In mathematical terms, you want to assign a color function c: {1, 2, \dots, n} \to \{1, -1\} such that for every edge \((u,v)\), it holds that \[ c(u) \times c(v) = -1. \]

If such an assignment exists, output "POSSIBLE"; otherwise, output "IMPOSSIBLE".

inputFormat

The input is given in the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Here, the first line contains two integers n and m representing the number of plots and the number of paths, respectively. The next m lines each contain two integers u and v indicating that there is a path between plot u and plot v.

outputFormat

Output a single line containing either "POSSIBLE" if the rides can be placed under the given condition, or "IMPOSSIBLE" if they cannot.

4 4
1 2
2 3
3 4
4 1

POSSIBLE