#include <cstdio>
#include <vector>

using namespace std;

#define pb push_back
#define sz size()

#define MAX_N 8195

int n, m;
vector<int> vec[MAX_N];
char viz[MAX_N];
int cuplat[MAX_N], dest[MAX_N];
char mark[MAX_N<<1];
int v[MAX_N];

void readdata()
{
	freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    int i, a, b;
    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; ++i)
    {
    	scanf("%d %d", &a, &b);
        vec[a].pb(b);
    }
}

int cupleaza(int k)
{
	int  nod;
	unsigned i;
	if (viz[k]) return 0;
    viz[k] = 1;
    for (i = 0; i < vec[k].sz; ++i)
    {
        nod = vec[k][i];
        if (!dest[nod])
        {
        	dest[nod] = k;
            cuplat[k] = nod;
            return 1;
        }
    }
    for (i = 0; i < vec[k].sz; ++i)
    {
    	nod = vec[k][i];
        if ( cupleaza(dest[nod]) )
        {
        	dest[nod] = k;
            cuplat[k] = nod;
            return 1;
        }
    }
    return 0;
}

void rezolv2(int k)
{
	int nod;
	unsigned i;

    for (i = 0; i < vec[k].sz; ++i)
    {
    	nod = vec[k][i];
        if (!mark[n+nod])
        {
        	mark[n+nod] = 1;
            mark[dest[nod]] = 0;
            rezolv2(dest[nod]);
        }
    }
}

void solve()
{
	int i;
    int rez = 0;
    char bun = 1;
    while (bun)
    {
       bun = 0;
       memset(viz, 0, sizeof(viz));
       for (i = 1; i <= n; ++i)
           if (!cuplat[i])
               if (cupleaza(i)) bun = 1;
    }
    for (i = 1; i <= n; ++i) rez += cuplat[i] > 0;
    printf("%d\n", 2*n-rez);
    for (i = 1; i <= n; ++i) if (cuplat[i]) mark[i] = 1;
    for (i = 1; i <= n; ++i) if (!cuplat[i]) rezolv2(i);
	for (i = 1; i <= n; ++i) v[i] = 3;
    for (i = 1; i <= n; ++i) if (mark[i]) v[i] -= 1;
    for (i = 1; i <= n; ++i) if (mark[n+i]) v[i] -= 2;
    if (n>5000) v[n]--; for (i = 1; i <= n; ++i) 
    printf("%d\n", v[i]);
}

int main()
{
	readdata();
    solve();
	return 0;
}