#include <iostream>
#include <vector>

using namespace std;

vector<int> G[8195];
int n , m ,x , y , cupl , r[8195] , l[8195];
bool u[8195] , ul[8195] , ur[8195];

int pairup(int node) 
{
    if (u[node]) return 0;
    u[node] = 1;
    for (vector<int>::iterator it = G[node].begin();it != G[node].end (); ++it)
        if (l[*it] == 0 || pairup(l[*it])) 
		{
           l[*it] = node, r[node] = *it, ul[node] = 1;
            return 1;
        }
    return 0;
}

void build_support(int node)
{
    for (vector<int>::iterator it = G[node].begin();it != G[node].end (); ++it)
    {
        if (!ur[*it])
        {
            ur[*it] = 1;
            ul[l[*it]] = 0;
			build_support(l[*it]);
        }
    }
    
}

int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(;m;m--)
	{
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
	}

	for(int change=1;change;)
	{
		change = 0;
		memset(u,0,sizeof(u));
		for(int i=1;i<=n;++i)
			if(!r[i])
				change|=pairup(i);
	}
	memset(u,0,sizeof(u));
	for(int i=1;i<=n;++i) cupl+=r[i]>0;

	for(int i=1;i<=n;++i)
		if(!ul[i]) build_support(i);

	printf("%d\n",n*2-cupl);

	for(int i=1;i<=n;++i)
		printf("%d\n",1-ul[i]+2*(1-ur[i]));

	return 0;
}