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

using namespace std;

const int maxn = 10000;

#define mkp make_pair
#define vii vector <int> :: iterator
#define vi vector<int>
#define pb push_back

vi VECT[maxn],VECTINV[maxn];
int VIZ[maxn],ST[maxn],DR[maxn];
int N,M,V[maxn],NR;
int MAS[maxn],MAD[maxn];
set <pair <int,int> > S;

bool cupleaza(int i)
{
	if (VIZ[i]) return 0;	
	VIZ[i] = 1;
	for(vii it = VECT[i].begin();it != VECT[i].end(); ++it)
		if (ST[*it] == 0) 
		{
			DR[i] = *it;
			ST[*it] = i;
			return 1;
		}
	for(vii it = VECT[i].begin();it != VECT[i].end(); ++it)
		if (cupleaza(ST[*it]))
		{
			DR[i] = *it;
			ST[*it] = i;
			return 1;
		}
	return 0;
}
/*
bool cupleazas(int i)
{	
	if (VIZ[i]) return 0;
	VIZ[i] = 1;
	for(vii it = VECTINV[i].begin();it != VECTINV[i].end(); ++it)
		if (DR[*it] == 0) return 1;
	for(vii it = VECTINV[i].begin();it != VECTINV[i].end(); ++it) if (cupleazas(DR[*it])) return 1;
	return 0;
}
*/

void cupleazad(int i)
{
/*    if (VIZ[i]) return 0;
	VIZ[i] = 1;*/
    for(vii it = VECT[i].begin();it != VECT[i].end(); ++it)
        if (S.find(mkp(*it,1)) == S.end()) 
		{
			S.insert(mkp(*it,1));
			int nod = ST[*it];
			S.erase(S.find(mkp(nod,0)));
			cupleazad(nod);
		}
}



int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d %d",&N,&M);
	for(int i = 1;i <= M; ++i)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		VECT[x].pb(y);
		VECTINV[y].pb(x);
	}
	bool move = 1;
//	printf("caca\n");
	while(move)
	{
		move = 0;
		memset(VIZ,0,sizeof(VIZ));
		for(int i = 1;i <= N; ++i)
		if (!DR[i] && cupleaza(i))	move = 1;			
	}
//	printf("caca\n");
	for(int i = 1;i <= N; ++i) V[i] = 3;
//	for(int i = 1;i <= N; ++i) printf("%d %d\n",i,DR[i]);
	for(int i = 1;i <= N; ++i)
	{
		if (DR[i]) S.insert(mkp(i,0));	
	}
	for(int i = 1;i <= N; ++i)
	{
		if (!DR[i]) cupleazad(i);	
	}
	for(set <pair <int,int> > :: iterator it = S.begin();it != S.end(); ++it)
	{
		int nod = (*it).first;
		V[nod] ^= ((*it).second + 1);
	}
	for(int i = 1;i <= N; ++i)
	{
		NR += ((V[i] & 1) != 0) + ((V[i] & 2) != 0);	
	}
	printf("%d\n",NR);
	for(int i = 1;i <= N; ++i)printf("%d\n",V[i]);
	return 0;
}