#include<fstream>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const char iname[]="felinare.in";
const char oname[]="felinare.out";
const int maxn=9000;

ifstream f(iname);
ofstream g(oname);

vector<int> E[maxn];

int l[maxn],r[maxn],n,i,m,k,been[maxn],beenr[maxn];

queue<int> Q;

int go(int x)
{
    if(been[x])
        return 0;
    been[x]=1;
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(!r[*it])
        {
            r[*it]=x;
            l[x]=*it;
            return 1;
        }

    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(go(r[*it]))
        {
            r[*it]=x;
            l[x]=*it;
            return 1;
        }

    return 0;
}

int main()
{
    f>>n>>m;

    //fac graful
    int x,y;
    for(i=1;i<=n;++i)
    {
        f>>x>>y;
        E[x].push_back(y);
    }

    //cuplaj maxim
    int ok=1;
    while(ok)
    {
        memset(been,0,sizeof(been));
        ok=0;
        for(i=1;i<=n;++i)
            if(!l[i])
                ok|=go(i);
    }


    //minimal vertex cover
    for(i=1;i<=n;++i)
        if(!l[i])
        {
            Q.push(i);
            been[i]=1;
        }

    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
            if(!beenr[*it])
            {
                beenr[*it]=1;
                if(r[*it]&&!been[r[*it]])
                    been[r[*it]]=1,Q.push(r[*it]);
            }
    }

    //rezultatul

    x=0;
    for(i=1;i<=n;++i)
        x+=(l[i]>0);
    g<<2*n-x<<"\n";
    for(i=1;i<=n;++i)
    {
        if(been[i])
            if(beenr[i])
                g<<1<<"\n";
            else
                g<<3<<"\n";
        else
            if(beenr[i])
                g<<0<<"\n";
            else
                g<<2<<"\n";
    }

    f.close();
    g.close();

    return 0;
}