#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

#define MAXN 8200
#define TIP(x) cout << #x << " = " << x << endl
#define DBG(x) (cout << __LINE__ << ": " << #x << " = " << (x) << endl)
#define pb push_back

int N, M;
vector <int> G[MAXN];
int d[MAXN], p[MAXN];
int viz[MAXN], iter;
int C[MAXN];

void read ()
{
    int a, b;
    for (scanf ("%d %d", &N, &M); M; -- M)
    {
        scanf ("%d %d", &a, &b);
        G[a].pb(b);
    }
}

int match (int n)
{
    if (viz[n] == iter) return 0;
    viz[n] = iter;
    
    int i, sz;
    for (i = 0, sz = (int)(G[n].size()); i < sz; ++ i)
        if (!d[G[n][i]])
        {
            d[G[n][i]] = n;
            p[n] = G[n][i];
            return 1;
        }
        else if (match(d[G[n][i]]))
        {
            d[G[n][i]] = n;
            p[n] = G[n][i];
            return 1;
        }
    return 0;
}

void A_Path(int n)
{
    if (viz[n] == iter) return;
    viz[n] = iter;
    
    p[n] = 0;
    int i, sz;
    for (i = 0, sz = (int)(G[n].size()); i < sz; ++ i)
        if (d[G[n][i]])
        {
            C[G[n][i]] = 1;
            A_Path(d[G[n][i]]);
        }
}

void solve ()
{
    int verif = 0, i;
    
    while (!verif)
    {
        verif = 1;
        ++ iter;
        for (i = 1; i <= N; ++ i)
            if (!p[i]) if (match(i))
            {
                verif = 1; 
                ++ iter;
            }
    }
    
    int sol = 2*N;
    
    for (i = 1; i <= N; ++ i)
    {
        //DBG (d[i]), DBG(i);
        ++ iter;
        if (d[i]) -- sol;
        if (!p[i]) A_Path(i);
    }
    printf ("%d\n", sol);
    
    for (i = 1; i <= N; ++ i)
        if (p[i] && C[i]) printf ("0\n");
        else if (!p[i] && C[i]) printf ("1\n");
        else if (p[i] && !C[i]) printf ("2\n");
        else printf ("3\n");
}

int
 main ()
{
    freopen ("felinare.in", "rt", stdin);
    freopen ("felinare.out", "wt", stdout);
    
    read ();
    solve ();
    
    return 0;
}