#include <bits/stdc++.h>

using namespace std;

ifstream fin ("felinare.in");
ofstream fout ("felinare.out");

struct nodS
{
    bool viz, use;
    int par;
    vector<int> v;
};

int n,m,i,x,y,nr;
nodS nod[17005];

bool tryCouple(int p)
{
    if(nod[p].viz)
        return false;

    int avoid=nod[p].par;

    for(int it : nod[p].v)
    {
        if(it==avoid)
            continue;

        if(!nod[it].par)
        {
            nod[p].par=it;
            nod[it].par=p;
            return true;
        }
    }

    for(int it : nod[p].v)
    {
        if(it==avoid)
            continue;

        if(tryCouple(nod[it].par))
        {
            nod[p].par=it;
            nod[it].par=p;
            return true;
        }
    }

    return false;
}
void match()
{
    bool ok=true;
    while(ok)
    {
        ok=false;

        for(int i=1;i<=n;i++)
            nod[i].viz=false;

        for(int i=1;i<=n;i++)
            if(!nod[i].par && tryCouple(i))
                ok=true;
    }
}
void dfs(int p)
{
    for(int it : nod[p].v)
    {
        if(!nod[it].use)
        {
            nod[it].use=true;

            int nxt=nod[it].par;
            nod[nxt].use=false;
            dfs(nxt);
        }
    }
}
void vcover()
{
    for(int i=1;i<=n;i++)
        if(nod[i].par)
            nod[i].use=true;

    for(int i=1;i<=n;i++)
        if(!nod[i].par)
            dfs(i);
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        nod[x].v.push_back(y+n);
        nod[y+n].v.push_back(x);
    }

    match();
    vcover();

    for(i=1;i<=2*n;i++)
    {
        nod[i].use^=1;

        if(nod[i].use)
            nr++;
    }

    fout<<nr<<'\n';
    for(i=1;i<=n;i++)
        fout<<nod[i+n].use+2*nod[i].use<<'\n';
    return 0;
}