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

using namespace std;

const int NMAX = 8192;

int N, M, sol;
vector <int> G[NMAX];
int st[NMAX], dr[NMAX], D[NMAX];
bool V[NMAX];

void read(void) {
	FILE *fin = fopen("felinare.in", "rt");
	int i, u, v;

	fscanf(fin, " %d %d", &N, &M);

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d", &u, &v);

		G[u].push_back(v);
	}

	fclose(fin);
}

bool pair_up(int u) {
	if (V[u]) return false;

	V[u] = true;

	int v, i;

	for (i = 0; i < (int) G[u].size(); ++i)
		if (!st[v = G[u][i]]) {
			dr[u] = v; st[v] = u; ++sol;
			return true;
		}
	
	for (i = 0; i < (int) G[u].size(); ++i)
		if (pair_up(st[v = G[u][i]])) {
			dr[u] = v; st[v] = u;
			return true;
		}
	
	return false;
}

void cuplaj(void) {
	int i;
	bool ok;

	do {
		memset(V, 0x00, sizeof(V));
		ok = false;

		for (i = 1; i <= N; ++i)
			if (!dr[i])
				ok |= pair_up(i);
	} while (ok);
}

void trip(int u) {
	int i, v;

	for (i = 0; i < (int) G[u].size(); ++i)
		if (!(D[v = G[u][i]] & 2)) {
			D[v] |= 2;
			D[st[v]] &= ~1;
			trip(i); 
			// poate sa iasa, pt ca nu mai face nimic, cred
		}
}

void suport(void) {
	int i;

	for (i = 1; i <= N; ++i)
		if (dr[i])
			D[i] |= 1;
	
	for (i = 1; i <= N; ++i)
		if (!dr[i])
			trip(i);
}

void write(void) {
	FILE *fout = fopen("felinare.out", "wt");
	int i;

	fprintf(fout, "%d\n", 2 * N - sol);

	for (i = 1; i <= N; ++i)
		fprintf(fout, "%d\n", D[i] ^ 3);

	fclose(fout);
}

int main(void) {

	read();

	cuplaj();

	suport();

	write();

	return 0;
}