#include<fstream>
#include<vector>
#include<cstring>
#define MMAX 20005
#define NMAX 8194
using namespace std;

ifstream f("felinare.in");
ofstream g("felinare.out");

int N,M,x,y,st[NMAX],dr[NMAX],U[NMAX],nr;

vector<int> L[NMAX];

int cupleaza(int nod)
{
    if (U[nod]) return 0;
    U[nod]=1;

    for (int i=0;i<L[nod].size();i++)
      if (!dr[ L[nod][i] ] || cupleaza( dr[ L[nod][i] ] ) )
      {
          st[nod]=L[nod][i];
          dr[L[nod][i]]=nod;
          return 1;
      }

    return 0;
}

int main()
{
    f>>N>>M;
    for (int i=1;i<=M;i++)
    {
        f>>x>>y;
        L[x].push_back(y);

    }

int    ok=1;
    while(ok)
    {
        memset(U,0,sizeof(U));
        ok=0;

        for (int i=1;i<=N;i++)
          if (!st[i])
            if ( cupleaza(i) )
            {   nr++;
                ok=1;
            }
    }

    g<<2*N-nr<<'\n';

    for (int i=1;i<=N;i++)
    {
        if (st[i]) g<<"2"<<'\n';
        else g<<"3"<<'\n';

    }

return 0;
}