#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4;

const int maxm = 2e5+;

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 = ; 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+,-,sizeof(int)*n);

        memset(deg+,,sizeof(int)*n);

        memset(col+,,sizeof(int)*n);

        ecnt = ;

        while(m--){

            int u,v;

            scanf("%d %d",&u,&v);

            addEdge(u,v); addEdge(v,u);

        }

        k = (*max_element(deg+,deg++n))|;

        memset(vis+,,sizeof(int)*k);

        dfs();

        printf("%d\n",k);

        for(int i = ; i <= n; i++) printf("%d\n",col[i]);

        putchar('\n');

    }

    return ;

}