You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

现在有编号为 $1,2,\dots,n$ 的共 $n$ 个格子，小 Z 要用 $1,2,3,4$ 共四种颜色对每一个格子进行染色。染色需要满足小 Y 给出 $m$ 条关系限制。每一条关系限制形如 a b，表示 $a$ 和 $b$ 格子必须染不同的颜色。

小 Y 给出的限制中，保证一个格子不会和多于 $3$ 其他个格子产生限制，即一个格子的限制不会超过 $3$ 条。

• 例如，对于 $4$ 号格子，如果出现了限制 4 1, 4 2, 4 3 三个限制，那么就不会再出现 4 5, 4,6 等 $4$ 号格子和其他格子的限制。

请你帮助小 Z 确定最终每个格子的合法染色方案，使得每个格子的颜色满足小 Y 的限制。

如果有多个合法的方案，输出染色的 $n$ 位数z中字典序最小的方案，也就是最小的 $n$ 位数。

输入格式

输入的第一行包含 $n$和 $m$，分别表示格子数量和限制条数。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示小 Y 的其中一条限制。

输出格式

输出一个 $n$ 位数，每一位均为 $1…4$ 之一，表示 $1,2,\dots,n$ 个格子，每个格子的颜色。如果有多种合法的染色方案，只需输出所有解中最小的 $n$ 位数。

样例 #1

样例输入 #1

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

样例输出 #1

12133

提示

【样例解释】

按照这种染色方案，$4$ 和 $1$ 不同，$4$ 和 $2$ 不同，$4$ 和 $3$ 不同，$2$ 和 $5$ 不同，$1$ 和 $2$ 不同，$1$ 和 $5$ 不同。

【数据范围】

$30\%$ 的数据，$2\le n \le 10, 1\le m \le 10$

$100\%$ 的数据，$2\le n \le 200,1\le m \le 150$。