#include <fstream>
//#include <iostream>
using namespace std;

ifstream f("felinare.in");
ofstream g("felinare.out");

#define pb push_back
int n,m;
#define LE 20666
#include <vector>
vector<int> H[LE];
int cpl[LE],i,j;
bool viz[LE],aprins[LE];
#define cout g

bool cupleaza(int nod){
 viz[nod]=true;
 int N=H[nod].size(),i;
 
   for(i=0;i<N;++i)
	if (cpl[H[nod][i]]==0){
		cpl[H[nod][i]]=nod;
		cpl[nod]=H[nod][i];
		return true;
	}else{
		if (viz[cpl[H[nod][i]]]==true) continue;
		
		if (cupleaza (cpl[H[nod][i]])){
		   cpl[nod]=H[nod][i];
		   cpl[H[nod][i]]=nod;
		   return true;
		}
	}
  
	return false;
}

int main(){
    f>>n>>m;
	
    for(i=1;i<=m;++i){
	   int xx,yy;
       f>>xx>>yy;
	   H[xx].pb(yy+n);
	   H[yy+n].pb(xx);
	}
	int res=0;
	for(i=1;i<=n;++i) if (cpl[i]==0){
		for(j=1;j<=n+m;++j) viz[j]=false;
	
		for(j=1;j<=n;++j) 
			if (viz[j]==false&&cpl[j]==false)
				if (cupleaza(j)) ++res;;
	}
	cout<<2*n-res<<'\n';
	
	for(i=1;i<=n+n;++i) 
		if (cpl[i]==0) aprins[i]=true;
	
	//for(i=1;i<=n;++i) if (cpl[i]) cout<<cpl[i]-n<<" "; else cout<<0<<" ";
//	cout<<'\n';
	//for(i=1;i<=n;++i) if (cpl[i+n]) cout<<cpl[i+n]<<" "; else cout<<0<<" ";
	//cout<<'\n';
	
		
	for(i=1;i<=n+n;++i) 
		if (aprins[i]==false){
			int N=H[i].size();
			aprins[i]=true;
			for(int j=0;j<N;++j) aprins[i]&=(!aprins[H[i][j]]);
	    }
	
	//for(i=1;i<=n+n;++i) if (aprins[i]) cout<<1<<" "; else cout<<0<<" ";
		
	for(i=1;i<=n;++i){
		int suma=0;
		if (aprins[i]==true) suma++;
		if (aprins[i+n]==true) suma+=2;
	    cout<<suma<<'\n';
	}
	
	
	return 0;
}