#include<fstream>
#include<vector>
#include<cstring>
using namespace std;

int i,j,n,m,x,y,c[17010],r[17010],ok,uz[17010],rez;
vector<int> a[17010];
int cuplaj(int nod)
{
	int i;
	if(uz[nod])
		return 0;
	uz[nod]=1;
	for(i=0;i<a[nod].size();++i)
		if(!c[a[nod][i]])
		{
			c[nod]=a[nod][i];
			c[a[nod][i]]=nod;
			return 1;
		}
		for(i=0;i<a[nod].size();++i)
			if(cuplaj(r[a[nod][i]]))
			{
				c[nod]=a[nod][i];
				c[a[nod][i]]=nod;
				return 1;
			}
			return 0;
}
void det(int nod)
{
	int i;
	for(i=0;i<a[nod].size();++i)
		if(!uz[a[nod][i]])
		{
			uz[a[nod][i]]=1;
			uz[c[a[nod][i]]]=0;
			det(c[a[nod][i]]);
		}
}
int main()
{
	FILE *f=fopen("felinare.in","r");
	FILE *g=fopen("felinare.out","w");
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d",&x,&y);
		a[x].push_back(y+n);
		a[y+n].push_back(x);
	}
	ok=0;
	while(!ok)
	{
		ok=1;
		memset(uz,0,sizeof(uz));
	for(i=1;i<=n;++i)
	if(!c[i]&&cuplaj(i))
		ok=0;
	}
	memset(uz,0,sizeof(uz));
	for(i=1;i<=n;++i)
		if(c[i])
			uz[i]=1;
		for(i=1;i<=n;++i)
			if(!c[i])
				det(i);
			rez=2*n;
	for(i=1;i<=n;++i)
		rez-=uz[i];
	fprintf(g,"%d\n",rez);
	for(i=1;i<=n;++i)
	{
		if(!uz[i]&&!uz[i+n])
			fprintf(g,"3\n");
		else
			if(!uz[i]&&!uz[i+n])
				fprintf(g,"1\n");
			else
				if(uz[i]&&!uz[i+n])
					fprintf(g,"2\n");
				else
					fprintf(g,"0\n");
	}
	return 0;
}