#include <cstdio>
#include <vector>

using namespace std;

#define file_in "felinare.in"
#define file_out "felinare.out"

#define nmax 1<<13

int n,m;
int viz[nmax];
int st[nmax];
int dr[nmax];
int l[nmax];
int r[nmax];
vector<int> G[nmax];

void citire()
{
	int i;
	int a,b;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
	}
}

int cupleaza(int nod)
{
	if (viz[nod])
		return 0;
	
	viz[nod]=1;
	
	for (int i=0;i<G[nod].size();++i)
	{
		int x=G[nod][i];
		if (!st[x])
		{
			dr[nod]=x;
			st[x]=nod;
			return 1;
		}
	}
	
	for (int i=0;i<G[nod].size();++i)
	{
		int x=G[nod][i];
		if (cupleaza(st[x]))
		{
			dr[nod]=x;
			st[x]=nod;
			return 1;
		}
	}
	
	return 0;
	
}

void doit(int nod)
{
	for (int i=0;i<G[nod].size();++i)
	{
		int x=G[nod][i];
		if (!l[x])
		{
			l[x]=1;
			r[st[x]]=0;
			doit(st[x]);
		}
	}
}

void solve()
{
	int ok=1,nr,i;
	
	while(ok)
	{
		ok=0;
		memset(viz,0,sizeof(viz));
		for (int i=1;i<=n;++i)
			if (!dr[i])
			ok|=cupleaza(i);
	}
	nr=0;
	for (int i=1;i<=n;++i)
		 if (dr[i]){
			 nr++;
			 l[i]=1;
		 }
	
		 	 
	printf("%d\n", (n<<1)-nr);
	memset(viz,0,sizeof(viz));
	
	for (i=1;i<=n;++i)
		 if (!dr[i])
			 doit(i);
		 
	for (i=1;i<=n;++i)
         if (l[i] && r[i])
			printf("0\n");
		 else
		 if (!l[i] && r[i])
			 printf("1\n");
		 else
		 if (l[i] && !r[i])
			printf("2\n");
         else
			printf("3\n");

	
	
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}