#include <bits/stdc++.h>
#define MaxN 8191
using namespace std;

vector<int> L[MaxN+1];
int is_l[MaxN+1];
int is_r[MaxN+1];
int viz[MaxN+1];
int cnt[MaxN+1];
int st[MaxN+1];
int dr[MaxN+1];
int N,M,K;

bool Cupleaza(int x)
{
    if(viz[x] == K) return 0;
    viz[x] = K;

    for(auto y : L[x])
    if(!dr[y])
    {
        st[x] = y;
        dr[y] = x;
        return 1;
    }

    for(auto y : L[x])
    if(Cupleaza(dr[y]))
    {
        st[x] = y;
        dr[y] = x;
        return 1;
    }

    return 0;
}

void DFS(int x)
{
    for(auto y : L[x])
    if(!is_r[y])
    {
        is_r[y] = 1;
        DFS(dr[y]);
    }
}

int main(){
    FILE* fin = fopen("felinare.in","r");
    FILE* fout = fopen("felinare.out","w");

    int i,A,B,gata,res=0;

    fscanf(fin,"%d %d",&N,&M);
    for(i = 1; i <= M; ++i)
    {
        fscanf(fin,"%d %d",&A,&B);
        L[A].push_back(B);
    }

    gata = 1;
    while(gata)
    {
        ++K;
        gata = 0;
        for(i = 1; i <= N; ++i)
        if(!st[i] && Cupleaza(i)) ++res, gata = 1;
    }

    fprintf(fout,"%d\n",2*N-res);
    for(i = 1; i <= N; ++i) viz[i] = 0;
    for(i = 1; i <= N; ++i)
    if(!st[i]) DFS(i);

    for(i = 1; i <= N; ++i)
    if(st[i] && !is_r[ st[i] ]) is_l[i] = 1;

    for(i = 1; i <= N; ++i)
        if(is_l[i] && is_r[i]) fprintf(fout,"0\n");
        else if(is_r[i]) fprintf(fout,"1\n");
        else if(is_l[i]) fprintf(fout,"2\n");
        else fprintf(fout,"3\n");


return 0;
}