#include <fstream>
#include <vector>
#define nmax 8195
using namespace std;
fstream f1("felinare.in", ios::in);
fstream f2("felinare.out", ios::out);
int n, m, viz[nmax], l[nmax], r[nmax], vizst[nmax], vizdr[nmax], maxi, sol[nmax];
vector<int> v[nmax];
void citire()
{
    int x, y;
    f1>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f1>>x>>y;
        v[x].push_back(y);
    }
}
int lant(int nod)
{
    viz[nod]=1;
    for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
        if(r[*it]==0)
    {
        r[*it]=nod;
        l[nod]=*it;
        return 1;
    }
   for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
       if((!viz[r[*it]])&&(lant(r[*it])))
     {
        r[*it]=nod;
        l[nod]=*it;
        return 1;
    }
   return 0;
}
void cuplaj()
{
    int i,f=1;
    while(f)
    {
        f=0;
        for(i=1; i<=n; i++)
            if(l[i]==0)
              f+=lant(i);
        for(i=1; i<=n; i++)
            viz[i]=0;
    }
}
void dfs(int nod)
{
    for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
        if(!vizdr[*it])
    {
        vizdr[*it]=1;
        vizst[r[*it]]=0;
        dfs(r[*it]);
    }
}
void min_cover()
{
    int i;
    for(i=1; i<=n; i++)
        if(l[i]!=0)
            vizst[i]=1;

    for(i=1; i<=n; i++)
        if(l[i]==0)
            dfs(i);
}
void afisare()
{
    ///max indep set= complem. min cover
    int i;
    for(i=1; i<=n; i++)
        {
            if(vizst[i]==0) {sol[i]+=1; maxi++;}
            if(vizdr[i]==0) {sol[i]+=2; maxi++;}
        }
    f2<<maxi<<"\n";
    for(i=1; i<=n; i++)
        f2<<sol[i]<<"\n";
}
int main()
{
    citire();
    cuplaj();
    min_cover();
    afisare();
    return 0;
}