#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];
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 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]] = cuplat[1][i] = 1;
		st[i] = 1; dr[i] = 2;
	}

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

	//lucrez pentru partea stanga
	for (i = 1; i <= n; i++)
		if (cuplat[0][i] == 0) {
			int len = A[i].size();
			for (j = 0; j < len; j++)
				dr[A[i][j]] = 0;
		}
          
	//lucrez pentru partea dreapta
	for (i = 1; i <= n; i++)
		if (cuplat[1][i] == 0) {
			int len = B[i].size();
			for (j = 0; j < len; j++)
				st[B[i][j]] = 0;
		}  

	//tai cuplajurile ramase
	for (i = 1; i <= n; i++)
		if (cuplaj[i] && cuplat[0][cuplaj[i]] && cuplat[1][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;
}