#include <stdio.h>
int n,m,i,x,y,cuplaj,ok,l[9001],r[9001],u[9001],s[18001];
struct nod{int a; nod *next;};
nod *G[9000];
int add(int a,int b)
{
    nod *nou=new nod;
    nou->a=b;
    nou->next=G[a];
    G[a]=nou;
    return 0;
}
int pair(int x)
{
    if (u[x]) return 0;
    u[x]=1;
    nod *it=new nod;
    it=G[x];
    while (it)
    {
        if (!r[it->a])
        {
            l[x]=it->a;
            r[it->a]=x;
            return 1;
        }
        it=it->next;
    }
    it=G[x];
    while(it)
    {
        if (pair(r[it->a]))
        {
            l[x]=it->a;
            r[it->a]=x;
            return 1;
        }
        it=it->next;
    }
    return 0;
}
int pair2(int x)
{
    nod *it=new nod;
    it=G[x];
    while (it)
    {
        if(!s[it->a])
        {
            s[it->a+n]=1;
            s[r[it->a]]=0;
            pair2(r[it->a]);
        }
        it=it->next;
    }
    return 0;
}
int main(void)
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    ok=1;
    while (ok)
    {
        ok=0;
        for (i=1;i<=n;i++) u[n]=0;
        for (i=1;i<=n;i++)
        {
            if (!l[i])
                ok|=pair(i);
        }
    }
    for (i=1;i<=n;i++)
    {
        if (l[i])
        {
            cuplaj++;
        }
    }
    for (i=1;i<=n;i++)
        if (l[i]) s[i]=1;
    for (i=1;i<=n;i++)
        if (!l[i]) pair2(i);
    printf("%d\n",2*n-cuplaj);
    int state;
    for (i=1;i<=n;i++)
    {
        state=0;
        if (!s[i]) state++;
        if (!s[i+n]) state+=2;
        printf("%d\n",state);
    }
    return 0;
}