#include <bits/stdc++.h>

using namespace std;

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

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

int n,m,x,y,nr,i;
nodS nod[18005];
bool tryCouple(int p)
{
    if(nod[p].viz)
        return false;

    int avoid=nod[p].par;
    nod[p].viz=true;

    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))
            {
                nr++;
                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<=m;i++)
    {
        fin>>x>>y;
        nod[x].v.push_back(y+n);
    }

    match();
    nr=2*n-nr;

    vcover();

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

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