#include <cstdio>
#include <vector>
#include <bitset>

#define maxN 8192
#define pb push_back

using namespace std;

int St[maxN], Dr[maxN], L[maxN], R[maxN];
int N, M, C;

vector <int> G[maxN];
bitset <maxN> U;

void ReadData()
{
	freopen("felinare.in", "rt", stdin);

	int a, b;
	for(scanf("%d %d", &N, &M); M; --M) {

		scanf("%d %d", &a, &b);
		G[a].pb(b);
	}

	fclose(stdin);
}

int PairUp(int nd)
{
	if(U[nd]) return 0;
	U[nd] = 1;

	vector <int> :: iterator it;

	for(it=G[nd].begin(); it!=G[nd].end(); ++it)
		if(!St[*it]) {
		
			Dr[nd] = *it;
			St[*it] = nd;
			L[nd] = 0;
			return 1;
		}

	for(it=G[nd].begin(); it!=G[nd].end(); ++it)
		if(!St[*it] || PairUp(St[*it])) {
		
			Dr[nd] = *it;
			St[*it] = nd;
			L[nd] = 0;
			return 1;
		}

	return 0;
}

int Cuplaj()
{
	memset(St, 0, sizeof(St));
	memset(Dr, 0, sizeof(Dr));

	int e = 1, i;
	while(e) {

		U = 0;
		e = 0;

		for(i=1; i<=N; ++i) if(!Dr[i]) e |= PairUp(i);
	}

	int ret = 0;
	for(i=1; i<=N; ++i) ret += (Dr[i] != 0);

	return ret;
}

void Suport(int nd)
{
	vector <int> :: iterator it;

	for(it=G[nd].begin(); it!=G[nd].end(); ++it)
		if(!R[*it]) {
		
			R[*it] = 1;
			L[St[*it]] = 0;

			Suport(St[*it]);
		}
}

void Solve()
{
	int i;
	for(i=1; i<=N; ++i)
		L[i] = R[i] = 1;

	C = Cuplaj();

	for(i=1; i<=N; ++i)
		if(L[i]) Suport(i);
}

void Write()
{
	freopen("felinare.out", "wt", stdout);

	printf("%d\n", (N<<1)-C);

	int i;
	for(i=1; i<=N; ++i)
		printf("%d\n", L[i]+2*R[i]);

	fclose(stdout);
}

int main()
{
	ReadData();
	Solve();
	Write();

	return 0;
}