#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("felinare.in");
ofstream fout ("felinare.out");

vector <int> l[8200];

int L[8200],R[8200],D[8200],v[8200],C,n,m,x,y,ok,i;

int cupleaza (int nod) {
    v[nod]=1;
    for (int i=0;i<l[nod].size();i++)
        if (!R[l[nod][i]]) {
            L[nod]=l[nod][i];
            R[l[nod][i]]=nod;
            return 1;
        }
    for (int i=0;i<l[nod].size();i++)
        if (!v[R[l[nod][i]]]&&cupleaza(R[l[nod][i]])){
            L[nod]=l[nod][i];
            R[l[nod][i]]=nod;
            return 1;
        }
    return 0;
}

void suport (int nod) {
    for (int i=0;i<l[nod].size();i++)
        if(!D[l[nod][i]]) {
            D[l[nod][i]]=1;
            L[R[l[nod][i]]]=0;
            suport (R[l[nod][i]]);
        }
}

int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        l[x].push_back(y);
    }
    do {
        ok=0;
        for (i=1;i<=n;i++)
            v[i]=0;
        for (i=1;i<=n;i++)
            if (!L[i]&&cupleaza(i)){
                ok=1;
                C++;
            }
    }while (ok);

    fout<<2*n-C<<"\n";

    for (i=1;i<=n;i++)
        if (!L[i])
            suport(i);
    for (i=1;i<=n;i++) {
        if (L[i]&&D[i])
            fout<<"0\n";
        else
            if (D[i])
                fout<<"1\n";
            else
                if (L[i])
                    fout<<"2\n";
                else
                    fout<<"3\n";
    }

    return 0;
}