Relaxed 4-Coloring of Graph

Given an undirected simple graph with n vertices and m edges, where no vertex has more than 7 neighbors, you are to color each vertex using exactly 4 different colors. In a usual proper coloring, adjacent vertices should have different colors. However, here the requirement is relaxed: for every vertex, at most one of its adjacent vertices is allowed to have the same color as itself.

Formally, let the colors be represented by numbers \(1,2,3,4\). For each vertex \(v\), if \(N(v)\) denotes the set of vertices adjacent to \(v\), and if \(c(u)\) is the color of vertex \(u\), the coloring is valid if for every vertex \(v\):

[ #{ u \in N(v) \mid c(u)=c(v) } \le 1. ]

Your task is to determine whether there exists a valid coloring that satisfies the condition stated above. If one exists, output one such coloring; otherwise, output impossible.

inputFormat

The first line contains two integers \(n\) and \(m\) (where \(1 \le n, m\le\text{(appropriate limits)}\)) — the number of vertices and edges in the graph.

The following \(m\) lines each contain two integers \(u\) and \(v\) (1-indexed) indicating that there is an undirected edge between vertices \(u\) and \(v\). It is guaranteed that the graph is simple (i.e. no self-loops or parallel edges) and that every vertex has at most 7 neighbors.

outputFormat

If a valid coloring exists, output a single line containing \(n\) integers where the \(i\)-th integer is the color (an integer between 1 and 4 inclusive) of vertex \(i\). If there are multiple solutions, any one is acceptable. Otherwise, output a single line containing the word impossible (without quotes).

sample

1 0

1