#include <bits/stdc++.h>
using namespace std;
ifstream f ("felinare.in");
ofstream g ("felinare.out");
const int nmax=1e4+3;
int n,m,k,sol,st[nmax],dr[nmax],viz[nmax],usu[nmax],a,b,ok;
vector <int> v[nmax];
int cuplaj(int nod)
{
	if(viz[nod]) return 0;
	viz[nod]=1;
	for(int i=0;i<v[nod].size();++i)
    {
        int urm=v[nod][i];
        if(!dr[urm])
		{
			st[nod]=urm;
			dr[urm]=nod;
			return 1;
		}
    }
	for(int i=0;i<v[nod].size();++i)
    {
        int urm=v[nod][i];
		if(cuplaj(dr[urm]))
		{
			st[nod]=urm;
			dr[urm]=nod;
			return 1;
		}
    }
	return 0;
}
void dfs(int nod)
{
	if(viz[nod]) return;
	viz[nod]=1;
	for(int i=0;i<v[nod].size();++i)
    {
        int urm=v[nod][i];
        if(st[nod]!=urm&&!usu[urm])
		{
			usu[urm]=1;
			dfs(dr[urm]);
		}
    }
}
int main()
{
    ios::sync_with_stdio(false);
	f>>n>>m;
	while(m--)
	{
		f>>a>>b;
		v[a].push_back(b);
	}
	ok=1;
	while(ok)
	{
		ok=0;
		memset(viz,0,sizeof(viz));
		for(int i=1;i<=n;++i)
        {
            if(!st[i])
            {
                if(cuplaj(i)) ok=1;
            }
        }
	}
	memset(viz,0,sizeof(viz));
	for(int i=1;i<=n;++i)
	{
		if(!st[i]) dfs(i);
		else ++sol;
	}
	for(int i=1;i<=n;++i)
	{
		dr[i]=0;
		if(viz[i])	++dr[i];
		if(!usu[i])	dr[i]+=2;
	}
	g<<2*n-sol<<'\n';
	for(int i=1;i<=n;++i) g<<dr[i]<<'\n';
    return 0;
}