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

vector<int> LL[MaxN+1];
vector<int> L[MaxN+1];
int luat[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;
}

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);
        LL[B].push_back(A);
        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])
        for(auto x : L[i]) luat[x] = 1;

    for(i = 1; i <= N; ++i)
    if(!dr[i])
        for(auto x : LL[i]) viz[x] = 1;

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

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


return 0;
}