#include <cstdio>
#include <list>
#include <cstring>
using namespace std;
#define MAX_N 8192
#define pb push_back
#define b begin
#define e end
typedef list<int> li;

li G[MAX_N], Gt[MAX_N];
int L[MAX_N], R[MAX_N], Sl[MAX_N], Sr[MAX_N];
int n,i;
bool U[MAX_N];

int PairUp(int x) {
	li::iterator i;
	if ( U[x] ) return 0;
	else		U[x] = 1;
	for (i=G[x].b(); i!=G[x].e(); ++i)
		if ( !R[*i] ) {
			R[*i] = x; L[x] = *i; Sr[*i] = 1; return 1;
		}
	for (i=G[x].b(); i!=G[x].e(); ++i)
		if ( PairUp(R[*i]) ) {
			R[*i] = x; L[x] = *i; Sr[*i] = 1; return 1;
		}
	return 0;
}

int C() {
	int c,i;
	for (c=0, i=1; i<=n; ++i)
		if ( PairUp(i) ) 
			c++;
		else {
			memset(U, 0, sizeof(U));
			c += PairUp(i);
		}
	return c;
}

void S(int x) {
	li::iterator i,j;
	for (i=G[x].b(); i!=G[x].e(); ++i)
		if ( !Sl[x] && !Sr[*i] ) {
			Sr[L[x]] = 0;
			Sl[x] = 1;
			for (j=Gt[*i].b(); j!=Gt[*i].e(); ++j)
				if ( !Sl[*j] ) 
					S(*j);
		}
}

void read_data();
int main() {
	read_data();

	freopen("felinare.out", "w", stdout);
	printf("%d\n", 2*n-C());
	for (i=1; i<=n; ++i)
		if ( !Sl[i] && L[i] )
			S(i);
	for (i=1; i<=n; ++i)
		printf("%d\n", Sl[i]*2+Sr[i]);
	return 0;
}

void read_data() {
	int m;

	freopen("felinare.in", "r", stdin);
	scanf("%d %d", &n, &m);
	while ( m-- ) {
		int x, y;
		scanf("%d %d", &x, &y);
		G[x].pb(y);
		Gt[y].pb(x);
	}
}