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

#define maxN 8192
#define pb push_back

using namespace std;

int St[maxN], Dr[maxN], Ret[maxN];
int N, M, C, Cm;

vector <int> G[maxN];
bitset <maxN> U, Us, Ud;

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] || Us[nd]) return 0;
	U[nd] = 1;

	vector <int> :: iterator it;

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

	for(it=G[nd].begin(); it!=G[nd].end(); ++it) if(!Ud[*it])
		if(!St[*it] || PairUp(St[*it])) {
		
			Dr[nd] = *it;
			St[*it] = nd;
			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 Solve()
{
	C = Cm = Cuplaj();

	int i;
	for(i=1; i<=N; ++i) {
	
		Us[i] = 1;
		int c = Cuplaj();
		
		if(c == C) {
			Ret[i] = 1;
			Us[i] = 0;
		}
		else if(c < C) C = c;

		Ud[i] = 1;
		c = Cuplaj();

		if(c == C) {

			Ret[i] += 2;
			Ud[i] = 0;
		}
		else if(c < C) C = c;
	}
}

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

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

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

	fclose(stdout);
}

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

	return 0;
}