#include<fstream>
#include<bitset>
#include<vector>
#define Nmax 8192
using namespace std;
vector<int> G[Nmax];
int N,M,r[Nmax],l[Nmax];
bitset<Nmax> sl;
bitset<Nmax> sr;
bitset<Nmax> u;
void read()
{
	ifstream f("felinare.in");
	f>>N>>M;
	int A,B,i;
	for(i=1;i<=N;++i)
	{
		f>>A>>B;
		G[A].push_back(B);
	}
	f.close();
}
int make_pair(int nod)
{
	if(u[nod])return 0;
	u[nod] = 1;
	for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
	if(!r[*it])
	{
		r[*it] = nod;
		l[nod] = *it;
		sl[nod] = 1;
		return 1;
	}
	for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
	if(make_pair(r[*it]))
	{
		r[*it] = nod;
		l[nod] = *it;
		sl[nod] = 1;
		return 1;
	}
	return 0;
}
void cuplaj()
{
	int change = 1,i;
	while(change)
	{
		change = 0;
		u.reset();
		for(i=1;i<=N;++i)
			if(!l[i])
				if(make_pair(i))change = 1;
	}
}
void sup(int nod)
{
	for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
	if(!sr[*it])
	{
		sr[*it] = 1;
		sl[r[*it]] = 0;
		sup(r[*it]);
	}
}
void support()
{
	int i;
	for(i=1;i<=N;++i)
		if(!sl[i])sup(i);
}
void write()
{
	ofstream g("felinare.out");
	g<<2*N-sl.count()-sr.count()<<"\n";
	int i;
	for(i=1;i<=N;++i)
	{
		if(sl[i] == 1 && sr[i] == 1)
			g<<"0\n";
		else if(!sl[i] == 1 && sr[i] == 1)
			g<<"1\n";
		else if(!sr[i] == 1 && sl[i] == 1)
			g<<"2\n";
		else g<<"3\n";
	}
	g.close();
}
int main()
{
	read();
	cuplaj();
	support();
	write();
	return 0;
}