#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
#define dim 20006
vector <int> v[dim];
int viz[dim],a[dim], b[dim],n,m,sol[dim*2];

void read()
{
    int i, x, y;
    fin>>n >>m;
    for(i=1;i<=m;++i)
    {
        fin>>x >>y;
        v[x].push_back(y);
    }
}

int pairup(int nod)
{
    if(viz[nod])
        return 0;
    viz[nod]=1;

    for(int k=0;k<(int)v[nod].size();++k)
        if(!b[v[nod][k]])
        {
            a[nod]=v[nod][k];
            b[v[nod][k]]=nod;
            return 1;
        }
    for(int k=0;k<(int)v[nod].size();++k)
        if(pairup(b[v[nod][k]]))
        {
            a[nod]=v[nod][k];
            b[v[nod][k]]=nod;
            return 1;
        }

    return 0;
}

void df(int nod)
{
    for(int k=0;k<(int)v[nod].size();++k)
        if(viz[v[nod][k]]==0)
        {
            viz[v[nod][k]]=1;
            sol[b[v[nod][k]]]=0;
            df(b[v[nod][k]]);
        }
}

void solve()
{
    int  ok;
    int nr=0;
    do
    {
        ok=0;
        memset(viz,0,sizeof(viz));
        for(int i=1;i<=n;++i)
            if(!a[i] && pairup(i))
            {
                ok=1;
                ++nr;
            }

    }while(ok);

    fout<<n*2-nr <<'\n';

    int i;

    memset(viz,0,sizeof(viz));
    for(i=1;i<=n;++i)
        if(a[i]!=0)
            sol[i]=1;

    for(i=1;i<=n;++i)
        if(a[i]==0)
            df(i);
}

void print()
{
    int i;
    for(i=1;i<=n;++i)
        if(sol[i] && viz[i])
            fout<<"0\n";
        else
            if(sol[i]==0 && viz[i]!=0)
                fout<<"1\n";
            else
                if(sol[i]!=0 && viz[i]==0)
                    fout<<"2\n";
                else
                    fout<<"3\n";
}

int main()
{
    read();
    solve();
    print();
    return 0;
}