#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 8192
#define Mmax 20005

#define pb push_back
#define sz size()

int n, m;
int dest[Nmax], v[Nmax], p[Nmax], w[Nmax], s[Nmax];
vector<int> lv[Nmax];

void citire()
{
    int i, a, b;
    
    scanf("%d %d\n", &n, &m);
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d\n", &a, &b);
        lv[a].pb(b);
    }
}

int cupleaza(int nod)
{
    int i, lim = lv[nod].sz;
    
    v[nod] = 1;
    
    for (i = 0; i < lim; ++i)
        if (!dest[lv[nod][i]])
        {
            p[nod] = lv[nod][i];
            dest[lv[nod][i]] = nod;
            return 1;
        }
    
    for (i = 0; i < lim; ++i)
        if (!v[dest[lv[nod][i]]] && cupleaza(dest[lv[nod][i]]))
        {
            p[nod] = lv[nod][i];
            dest[lv[nod][i]] = nod;
            return 1;
        }
    
    return 0;
}

void rezolva(int nod)
{
    int i, lim = lv[nod].sz;
    
    for (i = 0; i < lim; ++i)
        if (!w[lv[nod][i]])
        {
            w[lv[nod][i]] = 1;
            v[dest[lv[nod][i]]] = 0;
            rezolva(dest[lv[nod][i]]);
        }
}

void solve()
{
    int i, flux = 0, ok = 1;
    
    while (ok)
    {
        ok = 0;
        memset(v, 0, sizeof(v));
        for (i = 1; i <= n; ++i)
            if (!p[i] && cupleaza(i))
            {
                ++flux;
                ok = 1;
            }
    }
    
    memset(v, 0, sizeof(v));
    for (i = 1; i <= n; ++i)
        if (p[i])
            v[i] = 1;
    
    for (i = 1; i <= n; ++i)
        if (!v[i])
            rezolva(i);
    
    printf("%d\n", 2 * n - flux);
    for (i = 1; i <= n; ++i)
    {
        if (v[i] == 0)
            s[i] += 1;
        if (w[i] == 0)
            s[i] += 2;
    }
    for (i = 1; i <= n; ++i)
        printf("%d\n", s[i]);
}

int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    citire();
    solve();
    return 0;
}