#include<iostream>
#include<cstring>
#include<vector>

#define NMAX 10001

using namespace std;

vector<int> G[NMAX];
int deg[NMAX],l[NMAX],r[NMAX];
int n,m,ll[NMAX],rl[NMAX];

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

int pairup(int x)
{
	if(deg[x]) return 0;
	deg[x]=1;
	
	for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
		if(!r[*it]){r[*it]=x; l[x]=*it; return 1;}
	
	for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
		if(pairup(r[*it])){r[*it]=x; l[x]=*it; return 1;}
	
	return 0;
}

void rec(int x)
{
	for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
		if(!rl[*it])
		{
			rl[*it]=1;
			ll[r[*it]]=0;
			rec(r[*it]);
		}
}

void rezolvare()
{
	int ok=1;
	while(ok)
	{
		ok=0;
		memset(deg,0,sizeof(deg));
		for(int i=1;i<=n;i++)
			if(!l[i])
				ok!=pairup(i);
	}
	int i;
	for(i=1;i<=n;i++)
		if(l[i])
			ll[i]=1;
	for(i=1;i<=n;i++)
		if(!l[i])
			rec(i);
}

void afisare()
{
	int i,cp=2*n;
	for(i=1;i<=n;i++)
		if(l[i]>0)
			cp--;
	cout<<cp<<"\n";
	int ok;
	for(i=1;i<=n;i++)
	{
		ok=0;
		if(ll[i]  && !rl[i])
			ok=1;
		if(!ll[i] && rl[i])
			ok=2;
		if(ll[i] && rl[i])
			ok=3;
		cout<<3-ok<<"\n";
	}
}

int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	citire();
	rezolvare();
	afisare();
	return 0;
}