#include<cstdio>
#include<vector>

using namespace std;

int N, M, a[9000], C[9000], st[9000], dr[9000], vertex_cover_l[9000], vertex_cover_r[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;
}

void build_minimum_vertex_cover (int nod)
{
    for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
    {
        if (vertex_cover_r[*it])
            continue;
        vertex_cover_r[*it] = 1;
        vertex_cover_l[st[*it]] = 1;
        build_minimum_vertex_cover (st[*it]);
    }
}

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++)
    if (dr[i])
        cuplaj ++, vertex_cover_l[i] = 1;

for (int i=1; i<=N; i++)
    if (!vertex_cover_l[i])
        build_minimum_vertex_cover (i);

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

for (int i=1; i<=N; i++)
{
    int sol = 3;
    if (vertex_cover_l[i])
        sol ^= 1;
    if (vertex_cover_r[i])
        sol ^= 2;
    printf ("%d\n", sol);
}

return 0;
}