给定一个无向图，其中每个顶点的度数最多为 $5$。请用 $3$ 种颜色为它的顶点染色，使得每个顶点 $v$ 最多只有一个与其颜色相同的邻居。

输入格式

第一行包含两个整数 $n$ 和 $m$：顶点数和边数（$1 \le n \le 100\,000$）。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$：由一条边连接的两个顶点的编号（$1 \le a, b \le n$）。

保证图中无自环和重边，且每个顶点的度数最多为 $5$。

输出格式

如果不存在合法的染色方案，输出一个数字 “-1”（不含引号）。否则，输出 $n$ 个整数 $c_1, c_2, \dots, c_n$：所有顶点的颜色（$1 \le c_i \le 3$）。如果存在多种方案，输出其中任意一种即可。

样例

输入样例 1

3 3
1 2
2 3
1 3

输出样例 1

2 1 1

输入样例 2

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

输出样例 2

2 2 3 3 1 1

输入样例 3

3 1
1 2

输出样例 3

1 1 1