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

using namespace std;

#define lg 20000

int n, m, x, y, pus[lg], i, bag, rsp;
bool mark[lg], fst[lg];

vector<int> v[lg];

int leg(int nod){
	vector<int> :: iterator it;

	if (fst[nod])
		return 0;
	fst[nod] = 1;

	for (it = v[nod].begin(); it != v[nod].end(); it ++)
		if (!pus[ *it ]){
			pus[nod] = *it;
			pus[ *it ] = nod;

			return 1;
		}
	for (it = v[nod].begin(); it != v[nod].end(); it ++)
		if (leg(pus[ *it ])){
			pus[ *it ] = nod;
			pus[nod] = *it;

			return 1;
		}

	return 0;
}
void suport(int nod){
	for (vector<int> :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
		if (!mark[ *it ]){
			mark[ *it ] = 1;
			mark[ pus[ *it ] ] = 0;

			suport(pus[ *it ]);
		}
}

int main()
{
	freopen("felinare.in", "rt", stdin);
	freopen("felinare.out", "wt", stdout);

	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i ++){
		scanf("%d%d", &x, &y);

		v[x].push_back(n + y);
	}

	for (bag = 1; bag; ){
		bag = 0;
		memset(fst, 0, sizeof(fst));

		for (i = 1; i <= n; i ++)
			if (!pus[i])
				bag += leg(i);
	}

	for (i = 1; i <= n; i ++)
		if (pus[i])
			mark[i] = 1, rsp --;

	printf("%d\n", 2 * n + rsp);

	for (i = 1; i <= n; i ++)
		if (!pus[i])
			suport(i);

	for (i = 1; i <= n; i ++){
		int ans = 0;

		if (!mark[i])
			ans += 1;
		if (!mark[i + n])
			ans += 2;

		printf("%d\n", ans);
	}

	return 0;
}