#include <vector>
#include <stdio.h>
#include <string.h>
#include <time.h>
using namespace std;

#define MAXN 2*8192
#define MAX_M 20010
#define pb push_back

int N, M, res, sol[MAXN];
char viz[MAXN], pus[MAXN], p[MAX_M];

vector<int> G[MAXN], Ind[MAXN];

int pairup(int x)
{
    if(viz[x])
        return 0;

    viz[x] = 1;
    
    if(!pus[x] && x > N) { pus[x] = 1; return 1; }

    int i;

    for(i = (int)(G[x].size())-1; i >= 0; i--)
     if( ((p[Ind[x][i]] && x > N) || (!p[Ind[x][i]] && x <= N))
        && pairup(G[x][i]) ) { p[Ind[x][i]] ^= 1, pus[x] = 1; return 1; }

    return 0;
}

void dfs(int x)
{
    if(viz[x])
        return ;

    viz[x] = 1;

    int i;

    for(i = (int)(G[x].size())-1; i >= 0; i--)
     if( (p[Ind[x][i]] && x > N) || (!p[Ind[x][i]] && x <= N) )
        dfs(G[x][i]);
}

void solve(void)
{
    int i;

    for(i = 1; i <= N; i++)
     if(!pairup(i))
        memset(viz, 0, sizeof(viz)), res += pairup(i);
     else
        res++;

    memset(viz, 0, sizeof(viz));
    for(i = 1; i <= N; i++)
     if(!pus[i])
        dfs(i);

    for(i = 1; i <= N; i++)
     if(viz[i])
        sol[i] += 1;
    for(i = N+1; i <= 2*N; i++)
     if(!viz[i])
        sol[i-N] += 2;
}

int main(void)
{
    freopen("felinare.in", "rt", stdin);
    freopen("felinare.out", "wt", stdout);

    int i, a, b;
    int start, end;

    start = clock();

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= M; i++)
    {
        scanf("%d %d\n", &a, &b), b += N;
        G[a].pb(b), G[b].pb(a), Ind[a].pb(i), Ind[b].pb(i);
    }

    solve();

    printf("%d\n", 2*N-res);
    for(i = 1; i <= N; i++)
        printf("%d\n", sol[i]);
        
    end = clock();

    fprintf(stderr, "%lf\n", (double)(end-start)/CLOCKS_PER_SEC);
    
    return 0;
}