#include <cstdio>
#include <vector>

using namespace std;

const char iname[] = "felinare.in";
const char oname[] = "felinare.out";

#define MAXN  8192

vector <int> G[MAXN];

int l[MAXN], r[MAXN], sl[MAXN], sr[MAXN];  bool u[MAXN];

int n;


void read_in(void)
{
	FILE *fi = fopen(iname, "r");
	int x, y;
	int cnt;

	fscanf(fi, "%d %d", &n, &cnt);
	for (; cnt > 0; -- cnt) 
	{
		fscanf(fi, "%d %d", &x, &y);
		G[x].push_back(y);
	}
	fclose(fi);
}

int pairup(int n)
{
	if (u[n])
		return 0;
	u[n] = 1;
	vector <int>::iterator it;
	for (it = G[n].begin(); it != G[n].end(); ++ it) 
		if (!r[*it]) {
			l[n] = *it;
			r[*it] = n;
			sl[n] = 1;
			return 1;
		}
	for (it = G[n].begin(); it != G[n].end(); ++ it)
		if (pairup(r[*it])) {
			l[n] = *it;
			r[*it] = n;
			sl[n] = 1;
			return 1;
		}
	return 0;
}

void support(int n)
{
	vector <int>::iterator it;

	for (it = G[n].begin(); it != G[n].end(); ++ it)
		if (!sr[*it]) {
			sr[*it] = 1;
			sl[r[*it]] = 0;
			support(r[*it]);
		}
}

int main(void)
{
	read_in();
	
	int cnt = 0;
	for (int i = 1; i <= n; ++ i)
		if (!pairup(i)) {
			memset(u, 0, sizeof(u));
			cnt += pairup(i);
		} else
			cnt ++;

	for (int i = 1; i <= n; ++ i)
		if (!sl[i])
			support(i);
	for (int i = 1; i <= n; ++ i)
		sl[i] ^= 1, sr[i] ^= 1;

	FILE *fo = fopen(oname, "w");

	fprintf(fo, "%d\n", 2 * n - cnt);
	for (int i = 1; i <= n; ++ i)
	{
		if (sl[i] + sr[i] == 0)
			fprintf(fo, "0\n");
		else if (sl[i] && sl[i] + sr[i] == 1)
			fprintf(fo, "1\n");
		else if (sr[i] && sl[i] + sr[i] == 1)
			fprintf(fo, "2\n");
		else
			fprintf(fo, "3\n");
	}
	fclose(fo);

	return 0;
}