#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;

const int N=8200;


int L[N], R[N], LR[N], RR[N], n;
vector <int> GL[N], GR[N];
bitset <N> v;

int pairup(int x)
{
    if(v[x]) return 0;
    v[x]=1;
    for(auto p: GL[x])
    {
        if(!R[p])
        {
            L[x]=p;
            R[p]=x;
            return 1;
        }
    }
    for(auto p: GL[x])
    {
        if(pairup(R[p]))
        {
            L[x]=p;
            R[p]=x;
            return 1;
        }
    }
    return 0;
}

int cuplaj()
{
    int i, ok, ret=0;
    for(ok=1;ok;)
    {
        ok=0;
        v.reset();
        for(i=1;i<=n;i++) if(!L[i]) ok|=pairup(i);
    }
    for(i=1;i<=n;i++) if(L[i]) ret++;
    return ret;
}

void support(int x)
{
    for(auto p: GL[x])
    {
        if(!RR[p])
        {
            RR[p]=1;
            LR[R[p]]=0;
            support(R[p]);
        }
    }
}

int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    int i, x, y, sol;
    scanf("%d%d", &n, &i);
    while(i--)
    {
        scanf("%d%d", &x, &y);
        GL[x].push_back(y);
        GR[y].push_back(x);
    }
    sol=cuplaj();
    printf("%d\n", 2*n-sol);
    for(i=1;i<=n;i++)
    {
        if(L[i]) LR[i]=1;
        if(L[R[i]]!=i) R[i]=0;
    }
    for(i=1;i<=n;i++)
    {
        if(!LR[i])
        {
            support(i);
        }
    }
    for(i=1;i<=n;i++)
    {
        if(!LR[i]&&!RR[i]) printf("3\n");
        else if(!LR[i]) printf("1\n");
        else if(!RR[i]) printf("2\n");
        else printf("0\n");
    }
}