using namespace std;

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>

#include <cassert>

#define NDEBUG

#define FIN "felinare.in"
#define FOUT "felinare.out"

#define MAX_N 8192

int N, M, cnt;
int l[MAX_N], r[MAX_N], u[MAX_N], sl[MAX_N], sr[MAX_N];
vector <int> G[MAX_N];

void read()
{
	int a, b;
	scanf("%d %d", &N, &M);
	while (M--)
	{
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
	}
}

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 (!l[*it])
		{
			l[*it] = n;
			r[n] = *it;
			sl[n] = 1;
			return 1;
		}
	for (it = G[n].begin(); it != G[n].end(); ++it)
		if (pairup(l[*it]))
		{
			l[*it] = n;
			r[n] = *it;
			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[l[*it]] = 0;
			support(l[*it]);
		}
}

void solve()
{
	int i;
	for (i = 1; i <= N; ++i)
		if (!pairup(i))
		{
			memset(u, 0, sizeof(u));
			cnt += pairup(i);
		}
		else
			++cnt;
	for (i = 1; i <= N; ++i)
		if (!sl[i])
			support(i);
}

void write()
{
	int i;
	printf("%d\n", 2*N-cnt);
	for (i = 1; i <= N; ++i)
		printf("%d\n", 1-sl[i]+2*(1-sr[i]));
}

int main()
{
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	read();
	solve();
	write();

	return 0;
}