#include <stdio.h>
#include <vector>
#include <string>

using namespace std;

#define maxn 8192

int n,m,draw;
vector <int> a[maxn];
int g[maxn],mark[maxn],used[maxn];
int sol[maxn],s[2*maxn];

int DFS(int nod)
{
	int i;

	if (used[nod]==draw) return 0;
	used[nod]=draw;

	for (i=0;i<g[nod];i++)
		if (mark[a[nod][i]]==0) 
		{
			mark[a[nod][i]]=nod;
			s[nod]=1;
			return 1;
		}

	for (i=0;i<g[nod];i++)
	   if ((mark[a[nod][i]]!=0) && (DFS(mark[a[nod][i]])))
	   {
		   s[mark[a[nod][i]]]=0;
		   mark[a[nod][i]]=nod;
		   s[nod]=1;
		   return 1;
	   }

    return 0;
}

int cuplaj()
{
	int i,rez=0;

	for (i=1;i<=n;i++)
	{
		++draw;
		rez+=DFS(i);
	}

	return rez;
}

void DFS2(int nod)
{
	int i;

	for (i=0;i<g[nod];i++)
		if (!s[n+a[nod][i]])
		{
			s[n+a[nod][i]]=1;
			s[mark[a[nod][i]]]=0;
			DFS2(mark[a[nod][i]]);
		}
}

int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);

	scanf("%d %d ",&n,&m);

	int i,x,y;

	for (i=1;i<=m;i++)
	{
		scanf("%d %d ",&x,&y);
		a[x].push_back(y);
	}

	for (i=1;i<=n;i++) g[i]=a[i].size();

	printf("%d\n",2*n-cuplaj());

	for (i=1;i<=n;i++)
		if (!s[i]) DFS2(i);

	for (i=1;i<=n;i++)
	{
		if (!s[i]) sol[i]+=1;
		if (!s[i+n]) sol[i]+=2;
	}

	for (i=1;i<=n;i++) printf("%d\n",sol[i]);

	return 0;
}