#include <cstdio>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

const int NMAX=8191;

vector<int> G[NMAX];
int st[NMAX],dr[NMAX];
bool u[NMAX],v[NMAX];

bool pairup(int x)
{
    if (u[x]) return false;
    u[x]=true;
    vector<int>::iterator it;
    for (it=G[x].begin();it!=G[x].end();++it)
        if (st[*it]==-1)
        {
            dr[x]=*it;
            st[*it]=x;
            return true;
        }
    for (it=G[x].begin();it!=G[x].end();++it)
        if (pairup(st[*it]))
        {
            dr[x]=*it;
            st[*it]=x;
            return true;
        }
    return false;
}

void go(int x)
{
    u[x]=true;
    vector<int>::iterator it;
    for (it=G[x].begin();it!=G[x].end();++it)
       if (!v[*it] && dr[x]!=*it)
       {
           v[*it]=true;
           if (st[*it]==-1) continue;
           go(st[*it]);
       }
}      

int main()
{
    int N,M,i,j;
    ifstream fin("felinare.in");
    ofstream fout("felinare.out");
    
    fin>>N>>M;
    while (M--)
    {
        fin>>i>>j;
        --i;--j;
        G[i].push_back(j);
    }
    
    fill(dr,dr+N,-1);
    fill(st,st+N,-1);
    
    bool ok=true;
    while (ok)
    {
        ok=false;
        fill(u,u+N,false);
        for (i=0;i<N;++i)
            if (dr[i]==-1 && pairup(i)) ok=true;
    }
    
    fill(u,u+N,false);
    fill(v,v+N,false);
    for (i=0;i<N;++i)
        if (dr[i]==-1) go(i);

    int ans=0;
    for (i=0;i<N;++i)
    {
        if (u[i]) ++ans;
        if (!v[i]) ++ans;
    }
    
    fout<<ans<<"\n";
    for (i=0;i<N;++i)
    {
      int r=3;
      if (!u[i] && !v[i]) r=0;
      else if (u[i] && !v[i]) r=1;
      else if (!u[i] && v[i]) r=2;
      fout<<r<<"\n";
    }

    return 0;
}