#include <bits/stdc++.h>
using namespace std;

ifstream f("felinare.in");
ofstream g("felinare.out");

int n, m;
vector<vector<int>> vec;
vector<int> dr, st;
vector<bool> viz;

bool pairup(const int x){
	if(viz[x]) return false;
	viz[x] = true;

	for(int i = 0; i < 2; ++i){
		for(const auto y : vec[x]){
			if(i == 0 ? st[y] == -1 : pairup(st[y])){
				dr[x] = y;
				st[y] = x;
				return true; } } }
	return false; }

void build_cuplaj(){
	for(bool done_something = true; done_something; ){
		done_something = false;
		fill(begin(viz), end(viz), false);
		for(int i = 0; i < n; ++i){
			if(dr[i] == -1){
				done_something = (done_something ||
					pairup(i)); } } } }

vector<pair<int, int>> min_vertex_cover;

void recurse(const int x){
	if(viz[x]) return;
	viz[x] = true;
	for(const auto y : vec[x]){
		if(y == dr[x]) continue;
		min_vertex_cover.emplace_back(1, y);
		if(st[y] != -1) recurse(y); } }

void build_min_vertex_cover(){
	fill(begin(viz), end(viz), false);
	for(int i = 0; i < n; ++i){
		if(dr[i] == -1) recurse(i); }
	for(int i = 0; i < n; ++i){
		if(!viz[i]) min_vertex_cover.emplace_back(0, i); } }

int main(){
	f >> n >> m;
	vec.resize(n), st.resize(n, -1), dr.resize(n, -1), viz.resize(n, false);
	for(int i = 0, a, b; i < m; ++i){
		cin >> a >> b;
		vec[a-1].push_back(b-1); }
	
	build_cuplaj();
	build_min_vertex_cover();

	vector<int> rez(n, 3);

	for(const auto p : min_vertex_cover){
		rez[p.second] ^= (1<<p.first); }

	g << accumulate(begin(rez), end(rez), 0, [](const int x, const int y){
		const static int thing[] = { 0, 1, 1, 2 };
		return x + thing[y]; }) << '\n';
	for(const auto x : rez){
		g << x << '\n'; }
	return 0; }