#include <fstream>
#include <vector>
#define NMAx 8192
using namespace std;

vector <int> G[NMAx];
int N,NrC,Color,L[NMAx],R[NMAx];
bool SL[NMAx],SR[NMAx];
int viz[NMAx];

void SCuplaj(int nod) {
	
	int i,vecin;
	
	for(i=0;i<G[nod].size();i++)
		if(!SL[vecin = G[nod][i]]) {
			SL[vecin]=1;
			SR[L[vecin]]=0;
			SCuplaj(L[vecin]);
			}
		
}
bool Cuplaj(int nod) {
	
	int i,vecin;
	
	if(viz[nod]==Color)
		return 0;
	else
		viz[nod]=Color;
	
	for(i=0;i<G[nod].size();i++)
		if(L[vecin = G[nod][i]]==0||Cuplaj(L[vecin])) {
			R[nod]=vecin;
			L[vecin]=nod;
			SR[nod]=1;
			return 1;
			}
		
	return 0;
		
}
void Solve() {
	
	int nod,sw=1;
	
	while(sw) {
		sw=0;
		Color++;
		for(nod=1;nod<=N;nod++)
			if(!R[nod]&&Cuplaj(nod)) {
				sw=1;
				NrC++;
				}
		}
	
	for(nod=1;nod<=N;nod++)
		if(!SR[nod])
			SCuplaj(nod);
		
}
void Citire() {
	
	int i,x,y,M;
	ifstream in("felinare.in");
	
	in>>N>>M;
	
	for(i=1;i<=M;i++) {
		in>>x>>y;
		G[x].push_back(y);
		}
	
	in.close();
	
}
void Afis() {
	
	ofstream out("felinare.out");
	out<<(2*N-NrC)<<'\n';
	
	for(int i=1;i<=N;i++)
		out<<(1^SR[i]+((1^SL[i])<<1))<<'\n';
	
	out.close();
	
}
int main() {
	
	Citire();
	Solve();
	Afis();
	
	return 0;
	
}