// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<cstdio>
#include<vector>
#include<limits>
constexpr int NMAX=1<<14;

int N;

using T = int;

struct Dinic {
	struct Edge { int from, to, nxt; T cap, flow; };

	std::vector<Edge> es;
	std::vector<int> graph, at, dist, q;

	Dinic(int n) : graph(n, -1) {}

	int AddEdge(int a, int b, T c, bool dir = true) {
		auto add = [&](int a, int b, T c) {
			es.push_back({a, b, graph[a], c, 0});
			graph[a] = es.size() - 1;
		};
		add(a, b, c); add(b, a, dir ? 0 : c);
		return es.size() - 2;
	}
	bool bfs(int src, int dest) {
		dist.assign(graph.size(), -1); q.clear();
		dist[src] = 0; q.push_back(src);
		for (int i = 0; i < (int)q.size(); ++i) {
			int node = q[i];
			for (int ei = graph[node]; ei >= 0; ei = es[ei].nxt) {
				const auto &e = es[ei];
				if (dist[e.to] == -1 && e.cap > e.flow) {
					dist[e.to] = dist[node] + 1;
					q.push_back(e.to);
				}
			}
		}
		return dist[dest] != -1;
	}
	T dfs(int node, int dest, T need) {
		if (!need || node == dest) return need;
		T ret = 0;
		for (int ei = at[node]; ei != -1; ei = es[ei].nxt) {
			const auto &e = es[ei];
			if (dist[e.to] != dist[node] + 1) continue;
			if (T now = dfs(e.to, dest, std::min(need, e.cap - e.flow))) {
				es[ ei ].flow += now;
				es[ei^1].flow -= now;
				ret += now; need -= now;
			}
			if (!need) break;
		}
		return ret;
	}
	T Compute(int src, int dest) {
		T ret = 0;
		while (bfs(src, dest)) {
			at = graph;
			ret += dfs(src, dest, std::numeric_limits<T>::max());
		}
		return ret;
	}
	bool SideOfCut(int x) { return dist[x] == -1; }
};

Dinic D(NMAX);
int match[NMAX];
bool matched[NMAX];
bool Z[NMAX], vis[NMAX];

void dfs(int node, bool right)
{
	if(vis[node])
		return;
	vis[node]=1;
	Z[node]=1;

	if(right)
		return dfs(match[node], 0);

	for(int x=D.at[node];x>-1;x=D.es[x].nxt)
		if(!matched[node] || D.es[x].to!=match[node])
			dfs(D.es[x].to, 1);
}

int main()
{
	FILE* f=fopen("felinare.in", "r"), *g=fopen("felinare.out", "w");
	int i, a, b, M;

	fscanf(f, "%d%d", &N, &M);
	for(i=0;i<N;++i)
	{
		D.AddEdge(N*2, i, 1);
		D.AddEdge(N+i, N*2+1, 1);
	}
	for(i=0;i<M;++i)
	{
		fscanf(f, "%d%d", &a, &b);
		--a;
		--b;
		D.AddEdge(a, b+N, 1);
	}

	a=D.Compute(N*2, N*2+1);

	fprintf(g, "%d\n", N*2-a);
	for(auto e : D.es)
		if(e.from<N && e.flow==1)
		{
			// printf("%d %d'\n", e.from+1, e.to-N+1);
			matched[e.from]=1;
			matched[e.to]=1;
			match[e.from]=e.to;
			match[e.to]=e.from;
		}
	for(i=0;i<N;++i)
		if(!matched[i])
			dfs(i, 0);

	for(i=0;i<N;++i)
	{
		int x=3;
		if(!Z[i])
			x&=2;
		if(Z[i+N])
			x&=1;
		fprintf(g, "%d\n", x);
	}

	fclose(f);
	fclose(g);
	return 0;
}