#include <fstream>
#include <vector>
#include <cstring>
#define DIM 8200
using namespace std;
ifstream fi("felinare.in");
ofstream fo("felinare.out");
int n,m;
vector<int> V[DIM];
int ST[DIM],DR[DIM];
int rez;
int VIZ[DIM];
int VP[2][DIM];
bool cuplaj(int v)
{
    if(VIZ[v])
        return false;
    VIZ[v]=1;
    for(int i=0;i<V[v].size();i++)
        if(!DR[V[v][i]])
        {
            ST[v]=V[v][i];
            DR[V[v][i]]=v;
            return true;
        }
    for(int i=0;i<V[v].size();i++)
        if(cuplaj(DR[V[v][i]]))
        {
            ST[v]=V[v][i];
            DR[V[v][i]]=v;
            return true;
        }
    return false;
}
void dfs(int v,int p)
{
    if(VP[p][v])
        return;
    VP[p][v]=1;
    if(p==0)
        for(int i=0;i<V[v].size();i++)
            dfs(V[v][i],1);
    else
        if(DR[v])
            dfs(DR[v],0);
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        fi>>a>>b;
        V[a].push_back(b);
    }
    bool ok=true;
    while(ok)
    {
        ok=false;
        memset(VIZ,0,sizeof(VIZ));
        for(int i=1;i<=n;i++)
            if(!ST[i])
                if(cuplaj(i))
                    ok=true;
    }
    for(int i=1;i<=n;i++)
        if(ST[i])
            rez++;
        else
            dfs(i,0);
    fo<<2*n-rez<<"\n";
    for(int i=1;i<=n;i++)
        if(!VP[0][i]&&VP[1][i])
            fo<<0<<"\n";
        else if(VP[0][i]&&VP[1][i])
            fo<<1<<"\n";
        else if(!VP[0][i]&&!VP[1][i])
            fo<<2<<"\n";
        else
            fo<<3<<"\n";
    fi.close();
    fo.close();
    return 0;
}