题目描述

给定一张包含 $n$ 个结点和 $m$ 条边的简单无向图。请用尽可能少的颜色给所有结点染色，使得任意一条边的两个端点颜色不同。

输入格式

第一行包含两个整数 $n,m$，表示结点数和边数。结点编号为 $1,2,\ldots,n$。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示结点 $a$ 和 $b$ 之间有一条边。

输出格式

第一行输出一个整数 $k$，表示最少需要的颜色数。

第二行输出 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示每个结点的颜色，需满足 $1\le c_i\le k$。

可以输出任意一种合法最优染色方案。

数据范围

• $1 \le n \le 16$
• 0 \le m \le rac{n(n-1)}{2}

样例

样例输入

4 4
1 2
2 3
3 4
4 1

样例输出

2
1 2 1 2