#include <fstream>
#include <vector>
#define MAX 8200

using namespace std;

int n, nr[MAX], sr[MAX], sl[MAX], st[MAX], dr[MAX];
vector<vector<int> >g;
bool s[MAX];

bool cuplaj(int i)
{
	if (s[i]) return false;
	s[i] = 1;

	int j, p, x = g[i].size();
	for (p = 0; p < x; p++)
	{
		j = g[i][p];
		if (!st[j])
		{
			st[j] = i;
			dr[i] = j;
			sl[i] = 1;
			return true;
		}
	}
	for (p = 0; p < x; p++)
	{
		j = g[i][p];
		if (cuplaj(st[j]))
		{
			st[j] = i;
			dr[i] = j;
			sl[i] = 1;
			return true;
		}
	}
	return false;
}

void support(int i)
{
	int j, p, x = g[i].size();
	for (p = 0; p < x; p++)
	{
		j = g[i][p];
		if (!sr[j])
		{
			sr[j] = 1;
			sl[st[j]] = 0;
			support(st[j]);
		}
	}	
}

int main()
{
	int ok, i, v1, v2, m;

	ifstream fin("felinare.in");
	fin >> n >> m;

	g.resize(n+3);
	for (; m; m--)
	{
		fin >> v1 >> v2;
		g[v1].push_back(v2);
	}
	fin.close();

	int nr = 0;

	for (ok = 1; ok; )
	{
		memset(s, 0, sizeof(s));
		for (ok = 0, i = 1; i <= n; i++)
			if (!dr[i] && cuplaj(i))
			{
				nr++;
				ok = 1;
			}			
	}

	ofstream fout("felinare.out");
	fout << 2*n-nr << "\n";
	
	for (i = 1; i <= n; i++)
		if (!sl[i])
			support(i);		
	
	for (i = 1; i <= n; i++)
		fout << 1-sl[i] + 2*(1-sr[i]) << "\n";	
	
	fout.close();

	return 0;
}