#include <cstdio>
#include <cstring>
struct node {
	unsigned short key;
	node *next;
};


int n, m;
node *graph[16385];
unsigned short match[16385], queue[8192], dist[8193];

bool T[16385];

void add(int a, int b)
{
	node *q = new node;
	q->key = a;
	q->next = graph[b];
	graph[b] = q;
	
	q = new node;
	q->key = b;
	q->next = graph[a];
	graph[a] = q;
}

bool bfs()
{
	int left = 0, right = -1;
	for (int i = 1 ; i <= n ; ++i)
	{
		if (match[i] == 0)
		{
			dist[i] = 0;
			queue[++right] = i;
		}
		else
			dist[i] = 0xffff;
	}
	
	dist[0] = 0xffff;
	
	while (left <= right)
	{
		int nd = queue[left++];
		node *q = graph[nd];
		while (q)
		{
			if (dist[match[q->key]] == 0xffff)
			{
				dist[match[q->key]] = dist[nd] + 1;
				queue[++right] = match[q->key];
			}
			q = q->next;
		}
	}
	
	return dist[0] != 0xffff;
}

bool dfs(int nd)
{
	if (nd == 0)
		return true;
	node *q = graph[nd];
	while (q)
	{
		if (dist[match[q->key]] == dist[nd] + 1)
		{
			if (dfs(match[q->key]))
			{
				match[nd] = q->key;
				match[q->key] = nd;
				dist[match[q->key]] = 0xffff;
				return true;
			}
		}
		q = q->next;
	}
	
	dist[nd] = 0xffff;
	return false;
}

void addToMVC(int nd)
{
	T[nd] = true;
	node *q = graph[nd];
	while (q)
	{
		if (dist[match[q->key]] == dist[nd] + 1)
		{
			if (!T[match[q->key]])
			{
				T[q->key] = true;
				addToMVC(match[q->key]);
			}
		}
		q = q->next;
	}
}

int main()
{
	freopen("felinare.in", "r", stdin);
	freopen("felinare.out","w",stdout);
	
	scanf("%d%d", &n, &m);
	
	for (int i = 1 ; i <= m ; ++i)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b + n);
	}
	
	int matchCount = 0;
	
	while (bfs())
	{
		for (int i = 1 ; i <= n ; ++i)
			if (match[i] == 0 && dfs(i))
				matchCount++;
	}
	
	for (int i = 1 ; i <= n ; ++i)
		if (match[i] == 0)
			addToMVC(i);
	
	printf("%d\n", (n << 1) - matchCount);
	
	for (int i = 1 ; i <= n ; ++i)
	{
		printf("%d\n", ((T[i]) + ((1 - T[i + n]) << 1)));
	}
	
	return 0;
}