Graph Bipartition

You are given an undirected, unweighted graph with n vertices and m edges. Your task is to partition the vertices into two sets such that no edge has both of its endpoints in the same set.

If such a partition is possible, output POSSIBLE on the first line, followed by a line containing n integers where the i-th integer (either 1 or 2) denotes the set assignment of vertex i. Otherwise, output IMPOSSIBLE.

The problem is equivalent to checking whether the graph is bipartite. In mathematical notation, a graph G = (V, E) is bipartite if and only if its vertex set V can be divided into two disjoint subsets A and B (V = A ∪ B and A ∩ B = ∅) such that for every edge (u, v) in E, either u ∈ A and v ∈ B or u ∈ B and v ∈ A.

The correctness of your solution hinges on performing a breadth-first search (BFS) and properly alternating colors between adjacent nodes. If at any point two adjacent vertices are assigned the same color, the graph is not bipartite.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two space-separated integers n and m — the number of vertices and edges respectively.
• The following m lines each contain two space-separated integers u and v representing an edge between vertices u and v.

Note that the vertices are numbered from 1 to n.

outputFormat

If the graph can be partitioned into two sets such that no edge lies within the same set, output POSSIBLE on the first line, followed by a second line containing n integers (each either 1 or 2) that represent a valid partition of the vertices.

If the graph is not bipartite, output a single line with IMPOSSIBLE.

Output is written to stdout.

## sample

4 4
1 2
1 3
2 4
3 4

POSSIBLE
1 2 2 1

</p>