#include <stdio.h>
# include <vector>
# include <string.h>
using namespace std;
int nod,dr[9000],st[9000],nr,n,m,i,x,y;
bool use[18000],ok;

vector <int> v[9000];
bool cupleaza(int nod)
{
    int i;
    bool ok;
    if (use[nod]==true) return 0;
    use[nod]=true;
    for (i=1; i<=m; i++)
    {
        ok=false;
        for (int j=0; j<v[nod].size(); j++)
            if (v[nod][j]==i) {ok=true; break;}
        if (ok==true)
        {
            if (!dr[i] || cupleaza(dr[i]))
            {
                st[nod]=i;
                dr[i]=nod;
                return 1;
            }
        }
        else continue;
    }
    return 0;
}

void cuplaj()
{
    int i;
    for (i=1; i<=n; i++)
    {
        if (st[i]) continue;
        if (cupleaza(i)) nr++;
        else
        {
            memset(use,false,sizeof(use));
            if (cupleaza(i)) nr++;
        }
    }
}


void support(int nod)
{
    int i,t;
    for (i=0; i<v[nod].size(); i++)
    {
        t=v[nod][i];
        if (use[t+n]==false)
        {
            use[t+n]=true;
            use[dr[t]]=false;
            support(dr[t]);
        }
    }
}
int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d %d\n",&x,&y);
        v[x].push_back(y);
    }
    nr=0;
    cuplaj();
    printf("%d\n",2*n-nr);
    memset(use,false,sizeof(use));
    for (i=1; i<=n; i++)
        if (st[i]) use[i]=1;
    for (i=1; i<=n; i++)
       if (!st[i]) support(i);
    for (i=1; i<=n; i++)
    {
        x=3;
        if (use[i]) x--;
        if (use[n+i]) x-=2;
        printf("%d\n",x);
    }
    return 0;
}