Problem G
Groups of Strangers

Picture Image by macrovector at Freepik

A software company resulting from several recent mergers consists of a handful of offices in different cities. At each office there is a HR manager who knows everyone working at that office. Additionally, there are of course a lot of persons in the workforce that know each other, also across the offices. Knowing each other in this context is a symmetric relation, if employee $a$ knows employee $b$, then $b$ also knows $a$. In comparison, while everyone in the workforce (hopefully) knows of the CEO, that does not mean the CEO knows everyone. In fact, while the CEO does know all the HR managers, she does not know that many other employees. This has got to change!

One of the HR managers is instructed to plan a company outing to let people get to know each other better. Unfortunately, it seems impossible to a find a hotel that can accommodate the whole workforce. Maybe he can turn this into an advantage? He is thinking that by using up to three hotels in the vicinity of each other, perhaps it is possible to divide the employees in three groups, one per hotel, so that no two employees in a group already know each other? That would certainly encourage new acquaintances.

In this early stage in the planning, he doesn’t care about the sizes of the groups, but only wants to see if such a division is at all possible. He asks you to help him and provides you with a complete list of pairs of employees who know each other. However, you are not told who the HR managers or CEO are, but you know that the CEO knows at most $15$ employees (this includes the HR managers) and that the company is distributed over at most $8$ offices.

Input

The input consists of one line with the integers $N$ and $M$ ($2 \leq N \leq 1000, 1 \leq M \leq 100000$), the number of employees and the number of pairs of employees that know each other. Next follow $M$ lines each containing two integers $a$ and $b$ ($1\leq a\neq b \leq N$), indicating that employee $a$ knows employee $b$.

It is guaranteed that for the given test cases, there is at least one way to divide the employees into offices with HR managers and a CEO, like in the description. To summarize, the CEO is an employee who knows at most $15$ other people. The rest of the employees can be partitioned into at most $8$ offices, where each office has an employee (the HR manager) who knows all of the other employees in that office. In addition, the CEO knows all of the HR managers. Note that employees from different offices can know each other.

Output

If it is possible to divide the employees in at most three groups so that no pair that know each other are in the same group, output one row with the group identity $1,2,3$ for each employee in the same order they were numbered in the input. Use a single space between two subsequent employees’ group identities. If multiple solutions exist, you may output any. If no such group partitioning exists, output “Impossible”.

4 3
1 2
1 3
3 4

1 2 2 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Impossible