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

using namespace std;

#define MAX_N 8192

int n, m, i, p, q;
int fol[MAX_N], cuplaj[MAX_N], viz[MAX_N];
int marc_st[MAX_N], marc_dr[MAX_N], st[MAX_N], dr[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 calc(int nod, int k) {
	if (!k) {
		int len = A[nod].size();
		for (int i = 0; i < len; i++)
			dr[A[nod][i]] = 0;
	}
	else {
		int len = B[nod].size();
		for (int i = 0; i < len; i++)
			st[B[nod][i]] = 0;
	}
}

void dfs1(int nod) {
	int len = A[nod].size();
	for (int i = 0; i < len; i++)
		if (marc_dr[A[nod][i]] && cuplaj[A[nod][i]] != nod)	
			dr[A[nod][i]] = 0;
}

void dfs2(int nod) {
	int len = B[nod].size();
	for (int i = 0; i < len; i++)
		if (marc_st[B[nod][i]] && cuplaj[nod] != B[nod][i]) 
			st[B[nod][i]] = 0;
}

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--;
			}
	}

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

	for (i = 1; i <= n; i++)
		if (cuplaj[i]) {
			marc_dr[i] = 1;
			marc_st[cuplaj[i]] = 1;
		}

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

	//elimin nodurile din cuplaj care sunt legate de un nod care nu este in cuplaj	
	for (i = 1; i <= n; i++) {
		if (!marc_st[i])
			calc(i, 0);
		if (!marc_dr[i])
			calc(i, 1);
	}

	//mai am cazul cand sunt muchii intre doua noduri din cuplaje
	for (i = 1; i <= n; i++)
		if (cuplaj[i] && marc_st[cuplaj[i]] && !marc_dr[i])
			dfs1(i);
	for (i = 1; i <= n; i++)
		if (cuplaj[i] && !marc_st[cuplaj[i]] && marc_dr[i])
			dfs2(i);

	//in final, elimin muchiile ramase care formeaza efectiv cuplajul, daca mai sunt
	for (i = 1; i <= n; i++)
		if (st[cuplaj[i]] && dr[i])
			st[cuplaj[i]] = 0;
}           

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

int main() {

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

	return 0;
}