#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define file_in "felinare.in"
#define file_out "felinare.out"

#define Nmax 8192
#define Inf 0x3f3f3f3f
#define pb push_back
#define clear(a) memset(a,0,sizeof(a))

int cuplaj1[Nmax];
int cuplaj2[Nmax];
int n,m;
int viz[Nmax];
vector<int> v[Nmax];
int v1[Nmax];
int v2[Nmax];
int x[Nmax];

inline bool cupleaza(int nod)
{
	int i;
	if (viz[nod]==1) return false;
	viz[nod]=1;
	
    for (i=0;i<v[nod].size();++i)
	{
		if (!cuplaj2[v[nod][i]])
		{
			cuplaj1[nod]=v[nod][i];
			cuplaj2[v[nod][i]]=nod;
			return true;
		}
	}
	
	for (i=0;i<v[nod].size();++i)
	{
		if (cupleaza(cuplaj2[v[nod][i]]))
		{
			cuplaj1[nod]=v[nod][i];
			cuplaj2[v[nod][i]]=nod;
			return true;
		}
	}
	
	return false;
}	
	

void citire()
{
	int a,b,i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	for (i=0;i<m;++i)
	{
		scanf("%d %d", &a,&b);
		v[a].pb(b);
	}
}

void dfs(int nod) 
{   
    int i,x;   
    if (viz[nod]) return;   
    viz[nod]=1;   
               
    for (i=0;i<v[nod].size();++i) 
	{   
        x=v[nod][i];   
        if (!v1[x]) 
		{   
            v1[x]=1;   
            v2[cuplaj2[x]]=0;   
            dfs(cuplaj2[x]);   
        }   
    }   

}               


void solve()
{
	int i,ok,nrsol=0;   
    ok=1;   
    while(ok)
    {   
        ok=0;   
        clear(viz);   
        for(i=1;i<=n;++i) 
			if(!cuplaj1[i]) 
				ok|=cupleaza(i);   
    }   

	for (i=1;i<=n;++i)
          if (cuplaj1[i])
		  {
			 v2[i]=1;
			 nrsol++;
		  }
	
	printf("%d\n", 2*n-nrsol);
	
	//clear(v1);
	//clear(v2);
	 /*for (i=1;i<=n;++i)   
        if (cuplaj1[i])   
            v1[i]=1;   */
                   
    clear(viz);  
    for (i=1;i<=n;++i)   
        if (!cuplaj1[i])   
            dfs(i);   

	for (i=1;i<=n;++i)
	if (v1[i]==1 && v2[i]==1)   
            printf("0\n"); 
	else
	if (v1[i]==1 && v2[i]==0)   
            printf("1\n"); 
	else
	if (v1[i]==0 && v2[i]==1)   
            printf("2\n");
    else	
            printf("3\n");   

	
}   


int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}