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];

#ifndef NDEBUG
int stp;
#endif

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;
			//sr[*it] = 1;
			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]) {
#ifndef NDEBUG
			++stp;
#endif
			sr[*it] = 1;
			sr[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])
			sr[i] = 1;

	for (i = 1; i <= N; ++i)
		if (!sl[i])
			support(i);

#ifndef NDEBUG
	fprintf(stderr, "N = %d, flux = %d, pasi = %d\n", N, cnt, stp);
#endif
}

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;
}