#include <bits/stdc++.h>

using namespace std;

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

int n,m,i,x,y,sol,Left_[8200],Right_[8200];
vector<int> L[8200];
bitset<8200> f;

int cupleaza(int nod)
{
    if (f[nod])
        return 0;
    f[nod] = 1;
    for (int i=0; i<L[nod].size(); i++)
    {
        int vecin = L[nod][i];
        if (!Right_[vecin])
        {
            Left_[nod] = vecin;
            Right_[vecin] = nod;
            sol++;
            return 1;
        }
    }
    for (int i=0; i<L[nod].size(); i++)
    {
        int vecin = L[nod][i];
        if (cupleaza(Right_[vecin]))
        {
            Left_[nod] = vecin;
            Right_[vecin] = nod;
            return 1;
        }
    }
    return 0;
}

int main()
{
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
    }
    int ok = 0;
    do{
        ok = 0; f.reset();
        for (i=1; i<=n; i++)
            if (!Left_[i])
                ok = max(ok, cupleaza(i));
    } while (ok);
    fout << 2*n-sol << "\n";
    for (i=1; i<=n; i++)
    {
        if (!Left_[i] && !Right_[i])
            fout << 3 << "\n";
        if (!Left_[i] && Right_[i])
            fout << 1 << "\n";
        if (Left_[i] && !Right_[i])
            fout << 2 << "\n";
        if (Left_[i] && Right_[i])
            fout << 0 << "\n";
    }
    return 0;
}