#include <stdio.h>
#include <vector>
using namespace std;

#define Nmax 8200

vector <int> graph[Nmax];
int l[Nmax], r[Nmax], v[Nmax];
bool sl[Nmax], sr[Nmax];
int n, m, c;

void read(){
	freopen("felinare.in", "r", stdin);
	int u, v;

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i){
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
	}
	fclose(stdin);
}

int pairUp(int u){
	if (v[u])
		return 0;
	v[u] = 1;
	vector <int>::iterator it;

	for (it = graph[u].begin(); it != graph[u].end(); ++it)
		if (!r[*it] || pairUp(r[*it])){
			l[u] = *it;
			r[*it] = u;
			return 1;
		}
	return 0;
}

void vertexCover(int u){
	vector <int>::iterator it;

	for (it = graph[u].begin(); it != graph[u].end(); ++it)
		if (!sr[*it]){
			sr[*it] = true;
			sl[ r[*it] ] = false;
			vertexCover(r[*it]);
		}
}

void solve(){
	bool change = true;

	while (change){
		change = false;
		for (int i = 1; i <= n; ++i)
			v[i] = 0;
		for (int i = 1; i <= n; ++i)
			if (!l[i])
				if(pairUp(i)){
					++c;
					change = true;
				}
	}

	for (int i = 1; i <= n; ++i)
		if (l[i])
			sl[i] = true;
	for (int i = 1; i <= n; ++i)
		if (!sl[i])
			vertexCover(i);
}

void write(){
	freopen("felinare.out", "w", stdout);

	printf("%d\n", 2 * n - c);
	for (int i = 1; i <= n; ++i)
		if (sl[i] && sr[i])
			printf("0\n");
		else if (sl[i])
			printf("2\n");
		else if (sr[i])
			printf("1\n");
		else
			printf ("3\n");

	fclose(stdout);
}

int main(){
	read();
	solve();
	write();

	return 0;
}