#include<fstream>
#include<vector>
using namespace std;
int n,m,i,j,l[8200],r[16400],x,y,sol;
vector<int>a[8200];
int ok,uz[16400];
int cupleaza(int x)
{
    int i;
    if(uz[x]==1)
    return 0;
    uz[x]=1;
    for(i=0;i<a[x].size();++i)
    if(!r[a[x][i]])
    {
        l[x]=a[x][i];
        r[a[x][i]]=x;
        return 1;
    }

    for(i=0;i<a[x].size();++i)
    if(r[a[x][i]]&&cupleaza(r[a[x][i]]))
    {
        l[x]=a[x][i];
        r[a[x][i]]=x;
        return 1;
    }
}
void init()
{
    for(i=1;i<=n;++i)
    uz[i]=0;
}
void df(int x,int t)
{
    int i;
    if(uz[t]==0)
    uz[x]=2;
    else
    df(l[x]-n,x);
}
int main()
{
    ifstream f("felinare.in");
    ofstream g("felinare.out");
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        a[x].push_back(y+n);
    }
    ok=1;
    while(ok)
    {
        init();
        ok=0;
        for(i=1;i<=n&&!ok;++i)
        if(!l[i]&&cupleaza(i))
        ok=1;
    }
    sol=2*n;
    init();
    for(i=1;i<=n;++i)
    {
        if(!r[i]&&!uz[i])
        df(i,0);
        if(l[i])
        --sol;
        else
        ++uz[i];
    }
    g<<sol<<'\n';
    for(i=1;i<=n;++i)
    g<<uz[i]<<'\n';



}