#include <cstdio>
#include <vector>
#include <bitset>

const int MAX_N(9000);
const int MAX_M(20005);

int n, m, Result;
std::vector<int> Graph [MAX_N << 1];
int Left [MAX_N];
int Right [MAX_N << 1];
std::bitset<MAX_N> Mark;

inline void Read (void)
{
	std::freopen("felinare.in","r",stdin);
	std::scanf("%d %d",&n,&m);
	int i, a, b;
	for (i = 1 ; i <= m ; ++i)
	{
		std::scanf("%d %d",&a,&b);
		Graph[a].push_back(n + b);
		Graph[n + b].push_back(a);
	}
	std::fclose(stdin);
}

inline void Print (void)
{
	std::freopen("felinare.out","w",stdout);
	std::printf("%d\n",n * 2 - Result);
	for (int i(1) ; i <= n ; ++i)
		if (Mark[i] && Mark[i + n])
			std::printf("0\n");
		else if (Mark[i])
			std::printf("2\n");
		else if (Mark[i + n])
			std::printf("1\n");
		else
			std::printf("3\n");
	std::fclose(stdout);
}

bool DepthFirstSearch (int node)
{
	if (Mark[node])
		return false;
	Mark[node] = true;
	for (auto it : Graph[node])
		if (!Right[it] || DepthFirstSearch(Right[it]))
		{
			Left[node] = it;
			Right[it] = node;
			return true;
		}
	return false;
}

inline void HopcroftKarp (void)
{
	int match(0);
	while (true)
	{
		for (int i(1) ; i <= n ; ++i)
			if (!Left[i] && DepthFirstSearch(i))
				++match;
		if (match)
			Result += match;
		else
			break;
		Mark.reset();
		match = 0;
	}
}

void MinimumVertexCover (int node)
{
	for (auto it : Graph[node])
		if (!Mark[it])
		{
			Mark[it] = true;
			Mark[Right[it]] = false;
			MinimumVertexCover(Right[it]);
		}
}

inline void MinimumVertexCover (void)
{
	Mark.reset();
	int i;
	for (i = 1 ; i <= n ; ++i)
		if (Left[i])
			Mark[i] = true;
	for (i = 1 ; i <= n ; ++i)
		if (!Mark[i])
			MinimumVertexCover(i);
}

int main (void)
{
	Read();
	HopcroftKarp();
	MinimumVertexCover();
	Print();
	return 0;
}