#include <cstdio>
#include <vector>
#include <bitset>
#define DIMN 8200

using namespace std;
bitset <DIMN> f;
vector <int> v[DIMN];
int l[DIMN],r[DIMN],s[2*DIMN];
int cuplez (int nod){
    int i,vecin;
    //if (nod==2)
    //printf ("%d\n",nod);
    if (f[nod])
        return 0;
    f[nod]=1;
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (!r[vecin]){ /// il cuplez direct
            l[nod]=vecin;
            r[vecin]=nod;
            return 1;
        }
    }
    //if (nod==2)
      //  printf ("%d\n",nod);
    f[nod]=1;
    /// altfel, caut alta modalitate
    for (i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if (cuplez (r[vecin])){ /// il pot cupla pe nod cu vecin
            l[nod]=vecin;
            r[vecin]=nod;
            return 1;
        }
    }
    return 0;
}
void check (int x){
    int i,y;
    /// vreau sa verific daca x are nevoie de cuplat
    for (i=0;i<v[x].size();i++){
        y=v[x][i];
        if (s[y]==0){
            s[y]=1;
            s[r[y]]=0;
            check(r[y]);
        }

    }
}
int main()
{
    FILE *fin=fopen ("felinare.in","r");
    FILE *fout=fopen ("felinare.out","w");
    int n,m,i,x,y,ok,sol;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(n+y);
    }
    do{
        ok=0;
        f.reset();
        for (i=1;i<=n;i++){
            if (l[i]==0)
                ok=(ok|cuplez(i));
        }
    }
    while (ok==1);

    for (i=1;i<=n;i++)
        if (l[i])
            s[i]=1; /// al i-lea din stanga e in multime
    for (i=1;i<=n;i++){
        if (!l[i])
            check(i);
    }
    sol=0;
    for (i=1;i<=2*n;i++)
        sol+=s[i];
    fprintf (fout,"%d\n",2*n-sol);
    for (i=1;i<=n;i++){
        if (s[i] && s[i+n])
            fprintf (fout,"0\n");
        else if (s[i] && !s[i+n])
            fprintf (fout,"2\n");
        else if (!s[i] && s[i+n])
            fprintf (fout,"1\n");
        else fprintf (fout,"3\n");
    }
    return 0;
}