#include <fstream>
#include <vector>
#define NMAX 8200
using namespace std;
ifstream fin ("felinare.in");
ofstream fout("felinare.out");

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

int DFS(int nod)
{
	int i;

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

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

	for (i=0;i<g[nod];i++)
	   if ((mark[G[nod][i]]!=0) && (DFS(mark[G[nod][i]])))
	   {
		   mark[G[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+G[nod][i]])
		{
			s[n+G[nod][i]]=1;
			s[mark[G[nod][i]]]=0;
			DFS2(mark[G[nod][i]]);
//			break;
		}
}

int main()
{
	int i,x,y;
    fin>>n>>m;
	for (i=1;i<=m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
	}

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

	fout<<2*n-cuplaj()<<'\n';

	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++) fout<<sol[i]<<'\n';

	return 0;
}