#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],sl[8200],sr[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; sl[nod] = 1;
            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; sl[nod] = 1;
            Right_[vecin] = nod;
            return 1;
        }
    }
    return 0;
}

void supp(int nod)
{
    for (int i=0; i<L[nod].size(); i++)
    {
        int vecin = L[nod][i];
        if (!sr[vecin])
        {
            sr[vecin] = 1;
            sl[Right_[vecin]] = 0;
            supp(Right_[vecin]);
        }
    }
}

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 (!sl[i])
            supp(i);
    for (i=1; i<=n; i++)
    {
        if (!sl[i] && !sr[i])
            fout << 3 << "\n";
        if (!sl[i] && sr[i])
            fout << 1 << "\n";
        if (sl[i] && !sr[i])
            fout << 2 << "\n";
        if (sl[i] && sr[i])
            fout << 0 << "\n";
    }
    return 0;
}