#include<cstdio>
#include<bitset>
#include<vector>
using namespace std;

const char in[]="felinare.in";
const char out[]="felinare.out";

const int N_Max = 8200;

vector<int>G[N_Max];
bitset<N_Max>u,sl, sr;
int r[N_Max], l[N_Max], N, M, cnt;

bool cuplaj(int x)
	{
		vector<int>::iterator it;
		if(u[x])return 0;
		u[x] = true;
		
		for(it = G[x].begin() ; it != G[x].end() ; ++it)
			if(!r[*it])
			{
				r[*it] = x;
				l[x] = *it;
				sr[x] = true;
				return true;
			}
		
		for(it = G[x].begin() ; it != G[x].end() ; ++it)
			if(cuplaj(r[*it]))
			{
				r[*it] = x;
				l[x] = *it;
				sr[x] = true;
				return true;
			}
		return false;
}

void solve(int x)
	{
		vector<int>::iterator it;
		for(it = G[x].begin(); it != G[x].end(); ++it)
			if(!sl[*it])
			{
				sl[*it] = true;
				sr[r[*it]] = false;
				solve(r[*it]);
			}
}


int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		
		scanf("%d %d", &N, &M);
		
		for(int i = 1, x, y; i <= M ; ++i)
		{
			scanf("%d %d", &x, &y);
			G[x].push_back(y);
		}
		
		for(int i = 1 ; i <= N ; ++i)
		if(!cuplaj(i)){
			u.reset();
			cnt += cuplaj(i);
		}
		else ++cnt;
		
		printf("%d\n", 2*N - cnt);
		
		for(int i = 1 ; i <= N  ; ++i)
			if(!sr[i])solve(i);
		
		for(int i = 1 ; i <= N ; ++i)
			if(sl[i] && sr[i])printf("0\n");
			else if(sl[i] && !sr[i])printf("1\n");
			else if(!sl[i] && sr[i])printf("2\n");
			else if(!sl[i] && !sr[i])printf("3\n");
		
		return 0;
}