#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <cctype>
#define MOD 8192
#define pb push_back
#define INF 0x3f3f3f3f
#define INFLL (1LL*INF*INF)
#define ll long long
#define NMAX 9000

using namespace std;

typedef pair<int, int> pii;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

int st[NMAX],dr[NMAX],n,supportst[NMAX],supportdr[NMAX],res[NMAX];
bool viz[NMAX];
vector<int> v[NMAX];

int cupleaza(int x) {
	if(viz[x]) return 0;
	viz[x]=1;
	for(auto it:v[x]) {
		if(st[it]==0) {
			st[it]=x;
			dr[x]=it;
			return 1;
		}
	}

	for(auto it:v[x]) {
		if(cupleaza(st[it])) {
			st[it]=x;
			dr[x]=it;
			return 1;
		}
	}
	return 0;
}

void findSupport(int x) {
	for(auto it:v[x]) {
		if(supportdr[it]==0) {
			supportdr[it]=1;
			supportst[st[it]]=0;
			findSupport(st[it]);
		}
	}
}

int main() {
    int m,i,ok=1,x,y,nr=0;

	fin>>n>>m;
	for(i=1;i<=m;++i) {
		fin>>x>>y;
		v[x].pb(y);
	}

	while(ok) {
		ok=0;

		memset(viz,0,sizeof(viz));
		for(i=1;i<=n;++i)
			if(dr[i]==0) ok|=cupleaza(i);
	}

	for(i=1;i<=n;++i)
		if(dr[i]) supportst[i]=1;

	for(i=1;i<=n;++i)
		if(!dr[i]) findSupport(i);

	/*for(i=1;i<=n;++i) {
		if(supportst[i]==0) {
			++res[i];
			++nr;
		}
		if(supportdr[i]==0) {
			res[i]+=2;
			++nr;
		}
	}*/

	for(i=1;i<=n;++i) {
		if(dr[i]) {
			res[i]=2;
			++nr;
		}
		else {
			nr+=2;
			res[i]=3;
		}
	}

	fout<<nr<<'\n';
	for(i=1;i<=n;++i) fout<<res[i]<<'\n';

    return 0;
}