题目描述

顶级秘密组织$C.M.$局（该组织非常神秘，以至于没有人知道$C.M.$代表什么。最常见的解释是"Crazy Madmen"（疯狂疯子），但组织领导层坚决否认这一说法，尽管这种否认显然是徒劳的。）接到了一项艰巨的任务。为了完成任务，必须动用$C.M.$局的所有特工。更糟糕的是，已知某些特工对彼此怀恨在心，或者由于其他原因无法良好合作。因此，为了提高效率，$C.M.$局的领导决定将下属分成若干小组，确保这些互相厌恶的特工对不在同一小组中。然而，任务的性质决定了小组数量不能超过$3$个。

起初，这似乎是一项简单的任务，但他很快发现组织中有一些相当令人不快的成员。这些"坏家伙"在这种组织中当然是必要的，因为有些任务根本无法用"温和"的方式解决。过去这类人更多，但经过最近的改革，规定组织中最多有$3$个（但至少有$1$个）这样的角色。然而，他发现每个普通（即非坏家伙）成员都至少讨厌其中一个坏家伙，这让他怀疑是否能够实现这样的分组。

你的任务是判断他的怀疑是否正确，或者是否有可能根据上述标准将特工分成最多$3$个小组。

输入格式

输入包含多个测试用例。

每个测试用例的第一行包含两个整数$1 \leq A \leq 500$和$R \geq 0$，用单个空格分隔。$A$表示组织中的特工数量，特工编号为$0$到$A-1$。$R$表示互相厌恶的特工对数。接下来的$R$行描述这些特工对，每行包含两个整数$0 \leq a1, a2 < A$，用单个空格分隔，表示编号为$a1$和$a2$的特工互相厌恶。每对互相厌恶的特工只被描述一次。

每个测试用例后跟一个空行。输入以一行两个$0$结束。

输出格式

输出包含多行。第$i$行输出对应于第$i$个输入测试用例。

如果可以将该测试用例中的特工分成最多$3$个小组，则对应的输出行描述一种可行的分组方案。如果有多种可能的分组方案，只需输出其中任意一种。该行包含$A$个整数，每个整数属于$\{0, 1, 2\}$，用单个空格分隔，其中第$i$个数表示编号为$i-1$的特工被分配到的小组编号。

如果无法将特工分成满足条件的小组，则对应的输出行包含字符串"The agents cannot be split"。

输入样例1

3 3
0 1
0 2
2 1

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

0 0

输出样例1

0 1 2
The agents cannot be split

来源

CTU公开赛2004