#include <cstdio>
#include <vector>

#define DIM 9000

using namespace std;

int N, M, l[DIM], r[DIM];
vector <vector <int> > A;
vector <bool> sel, sl, sr;

void Support(int X)
{
	int Y;
	for (int i = 0; i < A[X].size(); i++)
	{
		Y = A[X][i];
		if (!sr[Y])
		{
			sr[Y] = true;
			sl[l[Y]] = false;
			Support(l[Y]);
		}
	}
}

bool Cuplaj(int X)
{
	if (sel[X]) return false;
	sel[X] = true;
	int Y;
	for (int i = 0; i < A[X].size(); i++)
	{
		Y = A[X][i];
		if (l[Y] < 0)
		{
			l[Y] = X;
			r[X] = Y;
			sl[X] = true;
			return true;
		}
	}
	for (int i = 0; i < A[X].size(); i++)
	{
		Y = A[X][i];
		if (Cuplaj(l[Y]))
		{
			l[Y] = X;
			r[X] = Y;
			sl[X] = true;
			return true;
		}
	}
	return false;
}

int main()
{
	FILE *fin = fopen("felinare.in", "r");
	FILE *fout = fopen("felinare.out", "w");

	fscanf(fin, "%d%d", &N, &M);
	A.resize(N + 1);
	int x, y;
	for (int i = 1; i <= M; i++)
	{
		fscanf(fin, "%d%d", &x, &y);
		A[x].push_back(y);
	}
	
	sl.resize(N + 1);
	sr.resize(N + 1);
	memset(l, -1, sizeof(l));
	memset(r, -1, sizeof(r));
	int ok = 1, nr = 0;
	while (ok)
	{
		ok = 0;
		sel.clear();
		sel.resize(N + 1);
		for (int i = 1; i <= N; i++)
			if (r[i] < 0 && Cuplaj(i))
			{
				nr++;
				ok = 1;
			}
	}
	fprintf(fout, "%d\n", 2 * N - nr);

	for (int i = 1; i <= N; i++)
		if (!sl[i]) Support(i);
	for (int i = 1; i <= N; i++)
	{
		int x = sl[i] ? 1 : 0;
		int y = sr[i] ? 1 : 0;
		fprintf(fout, "%d\n", 1 - x + 2 * (1 - y));
	}

	fclose(fin);
	fclose(fout);
	return 0;
}