#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
int n,m,i,o[8200],gasit,cuplaj,p1[8200],p2[8200],x,y;
bool sl[8200],sr[8200];
vector<int> G[8200];
int match(int s)
{
    int i,z=G[s].size();
    if (o[s]) return 0;
    o[s]=1;
    for (i=0;i<z;i++)
        if (!p2[G[s][i]])
    {
        p1[s]=G[s][i];
        p2[G[s][i]]=s;
        return 1;
    }
    for (i=0;i<z;i++)
        if (match(p2[G[s][i]]))
    {
        p1[s]=G[s][i];
        p2[G[s][i]]=s;
        return 1;
    }
    return 0;
}
void suport(int s)
{
    int i,z=G[s].size();
    for (i=0;i<z;i++)
        if (!sr[G[s][i]])
    {
        sr[G[s][i]]=1;
        sl[p2[G[s][i]]]=0;
        suport(p2[G[s][i]]);
    }
}
int main()
{
    freopen ("felinare.in","r",stdin);
    freopen ("felinare.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%i%i",&x,&y);
        G[x].push_back(y);
    }
    gasit=1;
    while (gasit)
    {
        gasit=0;
        memset(o,0,sizeof(o));
        for (i=1;i<=n;i++)
            if (!p1[i]) gasit+=match(i);
    }
    for (i=1;i<=n;i++)
        if (p1[i])
    {
        cuplaj++;
        sl[i]=1;
    }
    for (i=1;i<=n;i++)
        if (!p1[i]) suport(i);
    printf("%i\n",2*n-cuplaj);
    for (i=1;i<=n;i++)
        if (sl[i]&&sr[i]) printf("0\n");
        else if (sl[i]&&!sr[i]) printf("2\n");
        else if (!sl[i]&&sr[i]) printf("1\n");
        else printf("3\n");
    fclose(stdin);
    fclose(stdout);
    return 0;
}