#include <fstream>
#include <vector>

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


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()
{
	fin>>n>>m;
	for(;m;m--)
	{
		fin>>x>>y;
		G[x].push_back(y);
	}

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

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

	fout<<n*2-cupl<<'\n';

	for(int i=1;i<=n;++i)
	fout<<1-ul[i]+2*(1-ur[i])<<'\n';
	return 0;
}