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

    for(i=0;i<a[x].size();++i)
    if(cupleaza(l[a[x][i]]))
    {
        l[x]=a[x][i];
        l[a[x][i]]=x;
        return 1;
    }
    return 0;
}
void df(int x)
{
    int i;
    for(i=0;i<a[x].size();++i)
        if(!uz[a[x][i]])
        {
            uz[a[x][i]]=1;
            uz[l[a[x][i]]]=0;
            df(l[a[x][i]]);
        }
}
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=0;
     while(!ok)
    {
        ok=1;
        memset(uz,0,sizeof(uz));
    for(i=1;i<=n;++i)
    if(!l[i]&&cupleaza(i))
        ok=0;
    }
    memset(uz,0,sizeof(uz));
    for(i=1;i<=n;++i)
        if(l[i])
            uz[i]=1;
        for(i=1;i<=n;++i)
            if(!l[i])
                df(i);
            sol=2*n;
    for(i=1;i<=2*n;++i)
        sol-=uz[i];
    g<<sol<<"\n";
    for(i=1;i<=n;++i)
    {
        if(!uz[i]&&!uz[i+n])
            g<<3<<"\n";
        else
            if(uz[i]&&!uz[i+n])
                g<<2<<"\n";
            else
                if(!uz[i]&&uz[i+n])
                    g<<1<<"\n";
                else
                    g<<0<<"\n";
    }


}