#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

#define pb push_back
#define tr(C, i) for (typeof((C).begin()) i = (C).begin(); i != (C).end(); ++i)

typedef vector<int> VI;
typedef vector<VI> VVI;

int N;
VVI G;
VI L, R;
vector<bool> U, cutl, cutr;

bool pairup(int u) {
	if (cutl[u] || U[u]) return false;
	U[u] = true;

	tr(G[u], vv)
		if (!cutr[*vv] && !R[*vv]) {
			L[u] = *vv;
			R[*vv] = u;
			return true;
		}

	tr(G[u], vv)
		if (!cutr[*vv] && pairup(R[*vv])) {
			L[u] = *vv;
			R[*vv] = u;
			return true;
		}

	return false;
}

int cuplaj() {
	fill(R.begin(), R.end(), 0);
	fill(L.begin(), L.end(), 0);

	for (bool changed = true; changed; ) {
		fill(U.begin(), U.end(), false);
		changed = false;
		for (int i = 1; i <= N; ++i)
			if (!L[i])
				changed |= pairup(i);
	}

	int cuplaj = 0;
	for (int i = 1; i <= N; ++i)
		if (L[i])
			++cuplaj;

	return cuplaj;
}

int main(int argc, char *argv[]) {
	int M, u, v;

	ifstream fin("felinare.in");
	fin >> N >> M;
	G.resize(N+1);
	while (M--) {
		fin >> u >> v;
		G[u].pb(v);
	}
	fin.close();

	U.resize(N+1);
	cutl.resize(N+1);
	cutr.resize(N+1);
	L.resize(N+1);
	R.resize(N+1);

	int c = cuplaj();
	int oc = c;
	
	for (int i = 1; i <= N; ++i) {
		cutl[i] = true;
		int nc = cuplaj();
		cutl[i] = false;
		if (oc == nc+1) {
			cutl[i] = true;
			oc = nc;
		}
		cutr[i] = true;
		nc = cuplaj();
		cutr[i] = false;
		if (oc == nc+1) {
			cutr[i] = true;
			oc = nc;
		}
	}

	ofstream fout("felinare.out");
	fout << 2*N - c << endl;
	for (int i = 1; i <= N; ++i) {
		if (cutl[i] && cutr[i])
			fout << 0 << endl;
		else if (cutl[i] && !cutr[i])
			fout << 2 << endl;
		else if (!cutl[i] && cutr[i])
			fout << 1 << endl;
		else fout << 3 << endl;
	}
	fout.close();

	return 0;
}