题目描述

一家软件公司最近经历了多次合并，现在由分布在不同城市的若干办公室组成。每个办公室都有一位 HR 经理，他认识该办公室里的所有人。除此之外，公司员工之间当然也有很多认识关系，甚至跨办公室也可能互相认识。

这里“认识”是一种对称关系：如果员工 $a$ 认识员工 $b$，那么 $b$ 也认识 $a$。相比之下，虽然公司里每个人大概都知道 CEO，但这并不意味着 CEO 认识所有人。事实上，CEO 虽然认识所有 HR 经理，但她认识的其他员工并不多。这个情况必须改变！

一位 HR 经理被安排策划一次公司出游，让大家更好地互相认识。不幸的是，似乎找不到一家能容纳全体员工的酒店。也许这反而可以变成优势？他考虑在附近使用最多三家酒店，把员工分成最多三组，每组住一家酒店，并要求同一组中任意两个员工都不能已经认识。这样应该能鼓励大家结识新朋友。

在计划初期，他并不关心每组人数，只想知道这样的分组是否可能。他向你提供了完整的员工认识关系列表。你不知道哪些人是 HR 经理或 CEO，但你知道 CEO 最多认识 $15$ 名员工（包括 HR 经理），公司最多分布在 $8$ 个办公室。

输入格式

第一行包含两个整数 $N,M$，分别表示员工人数和互相认识的员工对数。

接下来 $M$ 行，每行包含两个整数 $a,b$，表示员工 $a$ 和员工 $b$ 互相认识。

$$2\le N\le 1000,\qquad 1\le M\le 100000,\qquad 1\le a e b\le N$$

保证输入数据至少存在一种符合题目描述的办公室、HR 经理和 CEO 划分。具体来说：存在一名 CEO，他最多认识 $15$ 名其他员工；其余员工可以被划分到最多 $8$ 个办公室中，每个办公室存在一名员工（HR 经理），他认识该办公室中的所有其他员工；此外 CEO 认识所有 HR 经理。不同办公室的员工之间也可能互相认识。

输出格式

如果可以把员工划分到最多三组中，使得任意一组内部不存在一对互相认识的员工，则输出一行 $N$ 个整数，表示每名员工所属组别。组别编号只能为 $1,2,3$，输出顺序按员工编号从 $1$ 到 $N$。相邻两个数之间用一个空格分隔。若有多种方案，输出任意一种。

如果不存在这样的分组，输出：

Impossible

输入输出样例 #1

输入 #1

4 3
1 2
1 3
3 4

输出 #1

1 2 2 3

输入输出样例 #2

输入 #2

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

输出 #2

Impossible