#include <iostream>
#include <vector>

using namespace std;

vector<int> G[8195];
int n , m ,x , y , cupl , r[8195] , l[8195];
bool u[8195];

int pairup(const int nod)
{
	if(u[nod]) return 0;
	u[nod] = 1;
	for(int i=0;i<(int)G[nod].size();++i)
		if(!r[G[nod][i]])
		{
			l[nod] = G[nod][i];
			r[G[nod][i]] = nod;
			return 1;
		}
	for(int i=0;i<(int)G[nod].size();++i)
		if(pairup(r[G[nod][i]]))
		{
			l[nod] = G[nod][i];
			r[G[nod][i]] = nod;
			return 1;
		}
	return 0;
}

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

int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(;m;m--)
	{
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
	}

	for(int change=1;change;)
	{
		change = 0;
		memset(u,0,sizeof(u));
		for(int i=1;i<=n;++i)
			if(!l[i])
				change|=pairup(i);
	}
	memset(u,0,sizeof(u));
	for(int i=1;i<=n;++i) if(l[i]>0) cupl++ , u[i] = 1;
	for(int i=1;i<=n;++i)
		if(!l[i]) check(i);
	for(int i=1;i<=n*2;++i)
		u[i] = !u[i];

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

	for(int i=1;i<=n;++i)
		printf("%d\n",u[i]+2*u[i+n]);

	return 0;
}