#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<queue>
using namespace std;

#define NMAX 2*8191+2
#define pb push_back
#define mp make_pair
#define x first 
#define y second

vector <int> v[NMAX];
priority_queue < pair < int , int > > c;

int grad[NMAX],suport[NMAX],oldbest;

int main ()
{
	int n,m,i,x,y,nr;
	ifstream f("felinare.in");
	ofstream g("felinare.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y;
		v[x].pb(y+n);
		v[y+n].pb(x);
		grad[x]++;
		grad[y+n]++;
	}
	f.close();
	n=n+n;
	for(i=1;i<=n;i++)
		if(grad[i])
			c.push(mp(grad[i],i));
	while(c.empty()==0) {
		x=c.top().y;
		if(grad[c.top().y]!=c.top().x || suport[c.top().y]==1) {
			c.pop();
			continue;
		}
		c.pop();
		suport[x]=1;
		for(vector <int> :: iterator it=v[x].begin();it!=v[x].end();it++) 
			if(suport[*it]==0) {
				grad[*it]--;
				grad[x]--;
				if(grad[*it])
					c.push(mp(grad[*it],*it));
			}
	}
	nr=0;
	for(i=1;i<=n;i++)
		if(suport[i]) 
			nr++;
	n=n/2;
	g<<2*n-nr<<'\n';
	for(i=1;i<=n;i++) {
		if(suport[i]==1 && suport[i+n]==1)
			g<<"0";
		else if(suport[i]==0 && suport[i+n]==1)
			g<<"1";
		else if(suport[i]==1 && suport[i+n]==0)
			g<<"2";
		else if(suport[i]==0 && suport[i+n]==0)
			g<<"3";
		g<<'\n';
	}
	g.close();
	return 0;
}