#include<cstdio>
#include<vector>

using namespace std;

int N, M, a[9000], C[9000], st[9000], dr[9000];
vector < int > v[9000];

bool cup (int nod)
{
    if (C[nod])
        return 0;
    C[nod] = 1;

    for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end (); it ++)
        if (st[*it] == 0)
        {
            st[*it] = nod;
            dr[nod] = *it;
            return 1;
        }

    for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end (); it ++)
        if (cup (st[*it]) )
        {
            st[*it] = nod;
            dr[nod] = *it;
            return 1;
        }
    return 0;
}

int main ()
{
freopen ("felinare.in", "r", stdin);
freopen ("felinare.out", "w", stdout);

scanf ("%d %d", &N, &M);
while (M)
{
    M --;
    int x, y;
    scanf ("%d %d", &x, &y);
    v[x].push_back (y);
}

bool ok = 1;
while (ok)
{
    ok = 0;
    for (int i=1; i<=N; i++)
        C[i] = 0;
    for (int i=1; i<=N; i++)
        if (dr[i] == 0)
            ok |= cup (i);
}

int cuplaj = 0;
for (int i=1; i<=N; i++)
{
    a[i] = 3;
    if (dr[i])
        cuplaj ++, a[i] ^= 1;
}

printf ("%d\n", 2 * N - cuplaj);

for (int i=1; i<=N; i++)
    printf ("%d\n", a[i]);

return 0;
}