#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
#define mp make_pair
#define f first
#define s second
#define NMax 17000

using namespace std;

int N, cuplat[NMax], st[NMax], dr[NMax], U[NMax], cnt = 0;
int sell[NMax];
vector<int> G[NMax];
set< pair<int, int> > HEAP;
int deg[NMax];

int cupleaza(int nod)
{
    vector<int>::iterator it;

    if (U[nod]) return 0;
    U[nod] = 1;

    for (it = G[nod].begin(); it != G[nod].end(); it++)
        if (!dr[*it] || cupleaza(dr[*it]))
        { st[nod] = *it; dr[*it] = nod; return 1; }
        
    return 0;
}

void elimina(int nod)
{
    vector<int>::iterator it;
    set< pair<int, int> >::iterator sk;

    for (it = G[nod].begin(); it != G[nod].end(); it++)
    {
        sk = HEAP.find( mp(deg[*it], *it) );
        if (sk != HEAP.end())
        {
           HEAP.erase( mp(deg[*it], *it) );
           deg[*it]++;
           HEAP.insert( mp(deg[*it], *it) );
        }
    }
    HEAP.erase( mp(deg[nod], nod) );
    deg[nod] = 0;    
}

int main()
{
    int M, i, j, u, v, sz;
    vector<int>::iterator it;
    set< pair<int, int> >::iterator hd;
    
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);

    scanf("%d %d", &N, &M);
    
    for (; M; M--)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(N + v);
        
        G[N+v].push_back(u);
    }

    memset(U, 0, sizeof(U));
    for (i = 1; i <= N; i++)
    {
        if (st[i]) continue;
        
        if (cupleaza(i)) cnt++;
        else
        {
            memset(U, 0, sizeof(U));
            if (cupleaza(i)) cnt++;
        }
    }

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

    for (i = 1; i <= N; i++) cuplat[i] = st[i];
    for (i = N+1; i <= 2*N; i++) cuplat[i] = dr[i];
    
    for (i = 1; i <= 2*N; i++)
        for (it = G[i].begin(); it != G[i].end(); it++)
            deg[i]--;

    for (i = 1; i <= 2*N; i++)
        if (cuplat[i])
            HEAP.insert( mp(deg[i], i) );

    while (1)
    {
        sz = HEAP.size();
        if (sz == 0) break;

        hd = (HEAP.begin());

        sell[hd->s] = 1;
        u = hd->s;
        elimina(u);
        
        HEAP.erase( mp(deg[cuplat[hd->s]], cuplat[hd->s]) );
        cuplat[cuplat[hd->s]] = 0;
        
    }

    for (i = 1; i <= 2*N; i++)
        sell[i] = 1-sell[i];

    for (i = 1; i <= N; i++)
        if (sell[i] + sell[N+i] == 0)
            printf("0\n");
        else if (sell[i] + sell[N+i] == 1 && sell[i] == 1)
            printf("1\n");
        else if (sell[i] + sell[N+i] == 1 && sell[N+i] == 1)
            printf("2\n");
        else if (sell[i] + sell[N+i] == 2)
            printf("3\n");

    return 0;
}