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

using namespace std;

#define MAX_N 8192

int n, m, i, j, p, q;
int fol[MAX_N], cuplaj[MAX_N], viz[MAX_N];
int st[MAX_N], dr[MAX_N], cuplat[2][MAX_N], use[2][MAX_N];
vector <int> G[MAX_N], A[MAX_N], B[MAX_N];

void cit() {
    freopen("felinare.in", "r", stdin);
	freopen("felinare.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d", &p, &q);
		G[p].push_back(q);

		A[p].push_back(q);
		B[q].push_back(p);
	}
}

int cupleaza(int nod) {
	if (viz[nod] == 1) return 0;
	viz[nod] = 1;

	int len = G[nod].size();
	for (int i = 0; i < len; i++) 
		if (!cuplaj[G[nod][i]]) {
			cuplaj[G[nod][i]] = nod;
			fol[nod] = 1;
			return 1;
		}

	for (int i = 0; i < len; i++)
		if (cuplaj[G[nod][i]] != nod && cupleaza(cuplaj[G[nod][i]])) {
			cuplaj[G[nod][i]] = nod;
			fol[nod] = 1;
			return 1;
		}

	return 0;
}   

void dfs(int nod, int side) {
    if (use[side][nod]) return;
	else use[side][nod] = 1;

	if (side == 0) {
		int len = A[nod].size();
		for (int i = 0; i < len; i++)
			if (cuplat[1][A[nod][i]]) {
				dr[A[nod][i]] = 0;
				dfs(cuplat[1][A[nod][i]], side);
			}
			else dfs(A[nod][i], 1 - side);
			
	}
	else {
		int len = B[nod].size();
		for (int i = 0; i < len; i++)
			if (cuplat[0][B[nod][i]]) {
				st[B[nod][i]] = 0;
				dfs(cuplat[0][B[nod][i]], side);
			}
			else dfs(B[nod][i], 1 - side);
	}
}

void solve() {
	int ok = 1, sol = 2 * n;
	while (ok) {
		ok = 0;
		memset(viz, 0, sizeof(viz));

		for (i = 1; i <= n; i++)
			if (!fol[i] && cupleaza(i)) {
				ok = 1;
				sol--;
			}
	}

    for (i = 1; i <= n; i++) {
		if (cuplaj[i]) {
			cuplat[0][cuplaj[i]] = i;
			cuplat[1][i] = cuplaj[i];
		}
		st[i] = 1; dr[i] = 2;
	}

	printf("%d\n", sol);

	//lucrez pentru stanga
	for (i = 1; i <= n; i++)
		if (!cuplat[0][i])
			dfs(i, 0);

	//lucrez pentru dreapta
	for (i = 1; i <= n; i++)
		if (!cuplat[1][i])
			dfs(i, 1);          

	for (i = 1; i <= n; i++)
		if (cuplaj[i] && st[cuplaj[i]] && dr[i])
			dfs(i, 1);  
}           

void write() {
	for (i = 1; i <= n; i++)
		printf("%d\n", st[i] + dr[i]);
}

int main() {

    cit();
	solve();
	write();

	return 0;
}