#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e4 + 7;

vector <int> v[DIM];

bitset <DIM> vis;
bitset <DIM> p;

int st[DIM];
int dr[DIM];

bool cuplaj(int nod)
{
	if(vis[nod] == true)
		return false;
		
	vis[nod] = true;
	
	for(auto i : v[nod])
		if(dr[i] == 0)
		{
			st[nod] = i;
			dr[i] = nod;
			
			return true;
		}
	
	for(auto i : v[nod])
		if(cuplaj(dr[i]) == true)
		{
			dr[i] = nod;
			st[nod] = i;
			
			return true;
		}
	
	return false;
}

void dfs(int nod)
{
	if(vis[nod] == 1)
		return ;
	
	vis[nod] = 1;
	
	for(auto i : v[nod])
		if(st[nod] != i && p[i] == 0)
		{
			p[i] = 1;
			dfs(dr[i]);
		}
}

int main()
{
	int n, m;
	in >> n >> m;
	
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		in >> x >> y;
		
		v[x].push_back(y);
	}
	
	bool ok = true;
	
	while(ok == true)
	{
		ok = false;
		
		vis.reset();
		
		for(int i = 1; i <= n; i++)
			if(st[i] == 0 && cuplaj(i))
				ok = true;
	}
	
	vis.reset();
	
	int nr = 0;
	
	for(int i = 1; i <= n; i++)
		if(st[i] == 0)
			dfs(i);
		else
			nr++;
	
	for(int i = 1; i <= n; i++)
	{
		dr[i] = 0;
		
		if(vis[i] == 1) dr[i]++;
		if(p[i] == 0) dr[i] += 2;
	}
	
	out << 2 * n - nr << '\n';
	
	for(int i = 1; i <= n; i++)
		out << dr[i] << ' ';
}