using namespace std;
#include<cstdio>
#include<vector>
#include<cstring>
#define MAX_N 8192
vector<int>G[MAX_N];
int N,M;
int sr[MAX_N], sl[MAX_N];
int r[MAX_N], l[MAX_N];
bool viz[MAX_N];
int CPL;
inline bool pairUp(int x)
{
	if(viz[x]) return 0;
	unsigned i; int y;
	viz[x] = 1;
	for(i=0;i<G[x].size();++i)
	{
		y = G[x][i];
		if(!l[y])
		{
			l[y] = x;
			r[x] = y;
			return 1;
		}
	}
	for(i=0;i<G[x].size();++i)
	{
		y = G[x][i];
		if(pairUp(l[y]))
		{
			l[y] = x;
			r[x] = y;
			return 1;
		}
	}
	return 0;
}
void cuplaj()
{
	bool ok;
	int i;
	for(ok = 1; ok;)
	{
		ok = 0;
		memset(viz,0,sizeof(viz));
		for(i=1;i<=N;++i) if(!r[i]) ok|=pairUp(i);
	}
}
void suport_minim(int x) // x e nod din stanga
{
	int y;
	unsigned i;
	for(i=0;i<G[x].size();++i)
	{
		y = G[x][i];
		if(!sr[y])
		{
			sr[y] = 1;
			sl[ l[y] ] = 0;
			suport_minim(l[y]);
		}
	}
}
int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d%d",&N,&M);
	int i,x,y;
	while(M--)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
	}
	cuplaj();
	for(i=1;i<=N;++i)
		if(r[i]) { sl[i] = 1; ++CPL; }
	for(i=1;i<=N;++i)
		if(!r[i]) suport_minim(i);
	printf("%d\n",2*N - CPL);
	for(i=1;i<=N;++i)
	{
		if(sr[i] && sl[i]) printf("0\n");
		else if(!sl[i] && sr[i]) printf("1\n");
		else if(sl[i] && !sr[i]) printf("2\n");
		else printf("3\n");
	}
	return 0;
}