题意：在一个n个点的无向连通图中，n是奇数，k是使得所有点的度数不超过k的最小奇数，询问一种染色方案，使得相邻点的颜色不同。

题解：一个点和周围的点的颜色数加起来最大为它的度数+1；如果最大度数是偶数，那么k种颜色一定够了。如果最大度数是奇数，而且n是奇数，那么k种颜色也一定是足够的。 可以反证，最大度数的点是u，deg[u]是奇数，而且和u相邻的点颜色各不相同，那么与u的一个相邻点v，至少和deg[u]个颜色不同的点相邻，这样构造出来连通图点数一定是偶数，和n是奇数是矛盾的，所以不会出现颜色数为deg[u]+1的情况。

所以只要染色就好了。

#include
     
      using namespace std;const int maxn = 1e4;const int maxm = 2e5+5;int head[maxn],to[maxm],nxt[maxm],col[maxn],ecnt,deg[maxn];int vis[maxn];void addEdge(int u,int v){    deg[u]++;    to[ecnt] = v;    nxt[ecnt] = head[u];    head[u] = ecnt++;}int k;void dfs(int u){    for(int i = head[u]; ~i; i= nxt[i]){        vis[col[to[i]]] = u;    }    for(int i = 1; i <= k; i++) if(vis[i] != u) { col[u] = i; break; }    for(int i = head[u]; ~i; i= nxt[i]){        if(col[to[i]]) continue;        dfs(to[i]);    }}int main(){    //freopen("in.txt","r",stdin);    int n,m;    while(~scanf("%d",&n)){        scanf("%d",&m);        memset(head+1,-1,sizeof(int)*n);        memset(deg+1,0,sizeof(int)*n);        memset(col+1,0,sizeof(int)*n);        ecnt = 0;        while(m--){            int u,v;            scanf("%d %d",&u,&v);            addEdge(u,v); addEdge(v,u);        }        k = (*max_element(deg+1,deg+1+n))|1;        memset(vis+1,0,sizeof(int)*k);        dfs(1);        printf("%d\n",k);        for(int i = 1; i <= n; i++) printf("%d\n",col[i]);        putchar('\n');    }    return 0;}