#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;

#define NMAX 8192

vector <int> v[NMAX];
int st[NMAX],dr[NMAX],sst[NMAX],sdr[NMAX],viz[NMAX];

inline int cupleaza(int nod)
{
	viz[nod]=1;
	for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
		if(dr[*it]==0) {
			dr[*it]=nod;
			st[nod]=*it;
			return 1;
		}
		else if(viz[dr[*it]]==0) {
			if(cupleaza(dr[*it])) {
				dr[*it]=nod;
				st[nod]=*it;
				return 1;
			}
		}
	return 0;
}

inline int hopcroft_karp(int n)
{
	int i,ok,cuplaj;
	ok=1;
	while(ok) {
		ok=0;
		memset(viz,0,sizeof(viz));
		for(i=1;i<=n;i++)
			if(st[i]==0) 
				ok=ok+cupleaza(i);
	}
	cuplaj=0;
	for(i=1;i<=n;i++)
		cuplaj=cuplaj+(st[i]!=0);
	return cuplaj;
}

inline void support(int nod)
{
	for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
		if(sdr[*it]==0) {
			sdr[*it]=1;
			sst[dr[*it]]=0;
			support(dr[*it]);
		}
}

int main ()
{
	int n,m,x,y,i;
	ifstream f("felinare.in");
	ofstream g("felinare.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y;
		v[x].push_back(y);
	}
	f.close();
	g<<2*n-hopcroft_karp(n)<<'\n';
	for(i=1;i<=n;i++)
		sst[i]=st[i];
	for(i=1;i<=n;i++)
		if(sst[i]==0)
			support(i);
	for(i=1;i<=n;i++) {
		if(st[i]==1 && dr[i]==1)
			g<<"0";
		else if(st[i]==0 && dr[i]==1)
			g<<"1";
		else if(st[i]==1 && dr[i]==0)
			g<<"2";
		else g<<"3";
		g<<'\n';
	}
	g.close();
	return 0;
}