#include <stdio.h>
#include <vector>

const int nmax = 1 << 13;

using namespace std;

int st[nmax], dr[nmax], left[nmax], right[nmax], n, m, sol, used[nmax], crt;
vector<int> v[nmax];

bool cupleaza(int);
void calculeaza(int);

int main()
{
	freopen("felinare.in", "r", stdin);
	freopen("felinare.out", "w", stdout);

	int i, ok, a, b;

	scanf("%d %d", &n, &m);

	for(i = 1; i <= m; ++i)
	{
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
	}

	while(ok)
	{
		++crt;
		ok = 0;
		for(i = 1; i <= n; ++i)
		{
			if(!dr[i])
			{
				if(cupleaza(i))
				{
					ok = 1;
					++sol;
				}
			}
		}
	}

	sol = 2 * n - sol;
	printf("%d\n", sol);

	for(i = 1; i <= n; ++i)
	{
		if(dr[i])
		{
			left[i] = 1;
		}
	}
	for(i = 1; i <= n; ++i)
	{
		if(!dr[i])
		{
			calculeaza(i);
		}
	}

	for(i = 1; i <= n; ++i)
	{
		if(!left[i])
		{
			if(!right[i])
			{
				printf("3\n");
			}
			else
			{
				printf("1\n");
			}
		}
		else
		{
			if(!right[i])
			{
				printf("2\n");
			}
			else
			{
				printf("0\n");
			}
		}
	}

	return 0;
}

bool cupleaza(int nod)
{
	int i, sz = v[nod].size();
	if(used[nod] == crt)
	{
		return 0;
	}
	used[nod] = crt;
	for(i = 0; i < sz; ++i)
	{
		if(!st[v[nod][i]])
		{
			dr[nod] = v[nod][i];
			st[v[nod][i]] = nod;
			return 1;
		}
	}
	for(i = 0; i < sz; ++i)
	{
		if(cupleaza(st[v[nod][i]]))
		{
			st[v[nod][i]] = nod;
			dr[nod] = v[nod][i];
			return 1;
		}
	}
	return 0;
}

void calculeaza(int nod)
{
	int i, sz = v[nod].size();
	for(i = 0; i < sz; ++i)
	{
		if(!right[v[nod][i]])
		{
			left[st[v[nod][i]]] = 0;
			right[v[nod][i]] = 1;
			calculeaza(st[v[nod][i]]);
		}
	}
}