#include <stdio.h>
#define NM 10001

int n, m, l[NM], r[NM], sl[NM], sr[NM], u[NM];
int i, j, k, cup, ok;
typedef struct nod {
    int vf;
    nod* urm;
} NOD, *PNOD;
PNOD g[NM];

void Add(int i, int j);
int DFM(int nod);
void Cuplaj();
void Support(int nod);

int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for ( k = 1; k <= m; k++ )
        scanf("%d %d", &i, &j),
        Add(i, j);
    
    Cuplaj();
    
    printf("%d\n", 2*n-cup);
    for ( i = 1; i <= n; i++ )
        printf("%d\n", 1-sl[i]+2*(1-sr[i]));
        
    return 0;
}

void Add(int i, int j)
{
    PNOD q = new NOD;
    q->vf = j;
    q->urm = g[i];
    g[i] = q;
}

int DFM(int nod)
{
    if ( u[nod] ) return 0;
    u[nod] = 1;
    PNOD q;
    for ( q = g[nod]; q; q = q->urm )
        if ( r[q->vf] == -1 )
        {
            r[q->vf] = nod;
            l[nod] = q->vf;
            sl[nod] = 1;
            return 1;
        }
    for ( q = g[nod]; q; q = q->urm )
        if ( DFM(r[q->vf]) )
        {
            r[q->vf] = nod;
            l[nod] = q->vf;
            sl[nod] = 1;
            return 1;
        }
    return 0;
}

void Cuplaj()
{
    int i;
    for ( i = 1; i <= n; i++ )
        l[i] = r[i] = -1, u[i] = 0;
    for ( ok = 1; ok; )
    {
        for ( i = 0; i <= n; u[i] = 0, i++ );
        for ( ok = 0, i = 1; i <= n; i++ )
            if ( l[i] == -1 && DFM(i) )
                cup++, ok = 1;
    }
    for (i = 1; i <= n; ++i)
		if (!sl[i])
			Support(i);
}

void Support(int nod)
{
	for ( PNOD q = g[nod]; q; q = q->urm )
		if (!sr[q->vf]) 
			sr[q->vf] = 1,
			sl[r[q->vf]] = 0,
			Support(r[q->vf]);
}