#include <fstream>
#include <vector>

using namespace std;

int N, M;
vector<int> V[8200];
int wh[2][8200], total;
bool S[8200], is[2][8200];

bool couple(int x)
{
	if (S[x] == true) return false;
	S[x] = true;
	
	for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!wh[1][*it] || couple(wh[1][*it]))
		{
			wh[0][x] = *it;
			wh[1][*it] = x;
			is[0][x] = true;
			
			return true;
		}
	return false;
}
void changenow(int x)
{
	for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!is[1][*it])
		{
			is[1][*it] = true;
			is[0][wh[1][*it]] = false;
			changenow(wh[1][*it]);
		}
}

int main()
{
	ifstream fin("felinare.in");
	ofstream fout("felinare.out");
	
	fin >> N >> M;
	for (int i = 1, nod1, nod2; i <= M; ++i)
	{
		fin >> nod1 >> nod2;
		V[nod1].push_back(nod2);
	}
	
	bool change = true;
	while (change)
	{
		change = false;
		memset(S, 0, sizeof(S));
		
		for (int i = 1; i <= N; ++i)
			if (!wh[0][i])
			{
				int now = couple(i);
				total += now;
				change |= now;
			}
	}
	
	fout << 2 * N - total << '\n';
	
	/*
	
	  In independent set sunt 2 * N - total noduri.
	  Deci, nu fac parte total noduri, care este jumatate din numarul de noduri cuplate.
	  Presupun ca cele cuplate din stanga sunt inactive, si restul active.
	  Pentru fiecare nod activ din stanga, verific sa fie indeplinite conditiile.
	  Daca o conditie nu ste implinita, sting nodul respectiv. Trebuie aprins altul in loc, asa ca
	dezactivez nodul cu care este cuplat. Nu se poate sa nu fie cuplat cu nimeni (ar fi fost cuplat cu
	cel initial).
	
	*/
	
	for (int i = 1; i <= N; ++i)
		if (!is[0][i])
			changenow(i);
	
	for (int i = 1; i <= N; ++i)
	{
		int now = 0;
		if (!is[0][i]) now |= 1;
		if (!is[1][i]) now |= 2;
		
		fout << now << '\n';
	}
	
	fin.close();
	fout.close();
}