企业家矮人想要在弗罗茨瓦夫开展一项旅游向导业务。他的旅游团将乘坐巴士穿过城市，每当巴士经过一个有趣的景点时，车载音响系统就会播放该景点的录制解说。

矮人准备了一张地图，其中包含 $N$ 个景点（编号从 $1$ 到 $N$）以及 $M$ 条双向街道，每条街道连接一对景点。他的地图有一个惊人的特点：每个景点最多与 $7$ 条街道相连。每次旅游路线都是由 $3$ 个不同景点组成的序列，其中每两个连续的景点之间都由一条街道相连。

现在，在选择旅游路线之前，矮人需要准备景点的录制解说并聘请专业解说员。他只能负担得起 $4$ 名解说员，并且每个景点的解说只能录制一次，且只能由一名解说员完成。然而，企业家担心即使是最好的解说员的声音也会让听众感到单调，因此他决定，在任何可能的旅游路线中，这 $3$ 个景点的解说不能全部由同一名解说员完成。

矮人尚未决定任何具体的旅游路线，而他的录音室预约就在明天。请帮助他为景点分配解说员，使得在任何可能的旅游路线中，这些景点不会由同一名解说员进行解说。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$，分别表示矮人地图上的景点数量和街道数量。

接下来的 $M$ 行描述了连接景点的街道，其中第 $i$ 行包含两个空格分隔的整数 $a_i$ 和 $b_i$，表示这条街道连接的两个景点的编号。

输出格式

输出一行，包含 $N$ 个空格分隔的整数 $c_1, \dots, c_N$，其中 $c_i$ ($1 \le c_i \le 4$) 表示应该为第 $i$ 个景点录制解说的解说员编号。

如果存在多种解法，输出其中任意一种即可。你可以假设在每个测试用例中都存在至少一种解法。

数据范围

$1 \le N \le 10^6$

$1 \le M \le 3.5 \cdot 10^6$

$1 \le a_i, b_i \le N$

$a_i \neq b_i$

没有街道连接景点自身，

没有一对景点由多于一条街道连接，

每个景点最多与 $7$ 条街道相连。

样例

输入 1

3 3
1 2
2 3
3 1

输出 1

2 1 1

输入 2

8 13
1 2
1 3
1 4
1 5
1 6
1 7
2 3
3 4
4 5
5 6
6 7
7 8
8 2

输出 2

2 3 1 3 1 3 1 1