\(dfs+\)证明。
对于题目描述，可以发现\(K\)其实就是大于等于原图中最大度数的最小奇数，因为如果原图度数最大为奇数，则最多颜色肯定为K，而如果原图最大度数为偶数，则\(K\)又是奇数，则最多颜色也肯定小于等于\(K\)。
然后可以\(dfs\)染色,染色有两种方法，一种是枚举颜色，然后判断可行性并考虑回溯。这种搜索复杂度很大。
而另一种方法就是直接贪心搜索，使每个当前搜到的点取除去与它相连的颜色的最小值，然后并不需要判断可行性，因为每次都是将当前颜色尽可能的不相同。
#define N 300101
#include <bits/stdc++.h>
using namespace std;
struct edg {
int to, nex;
}e[N];
int n, m, k, cnt, lin[N], degree[N], color[N], flag[N];
inline void add(int f, int t)
{
degree[f]++;
e[++cnt].to = t;
e[cnt].nex = lin[f];
lin[f] = cnt;
}
void dfs(int now)//now的颜色要取除去与它相连的颜色 的最小值，因为这样才能将每个颜色都利用
{
// int sum = 0;
memset(flag, 0, sizeof(flag));
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (color[to])
flag[color[to]] = 1;
}
for (int i = 1; i <= k; i++)
if (!flag[i])
{
color[now] = i;
break;
}
for (int i = lin[now]; i; i = e[i].nex)
if (!color[e[i].to])
dfs(e[i].to);
}
inline void clear()
{
memset(e, 0, sizeof(e));
memset(lin, 0, sizeof(lin));
memset(degree, 0, sizeof(degree));
memset(color, 0, sizeof(color));
k = cnt = 0;
}
int main()
{
while (cin >> n >> m)
{
clear();
for (int i = 1; i <= m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++)
k = max(k, degree[i]);
k |= 1;
printf("%d\n", k);
dfs(1);
for (int i = 1; i <= n; i++)
printf("%d\n", color[i]);
puts("");
}
}