/*
 * File:   main.cpp
 * Author: petru
 *
 * Created on 2010-09-17
 */


#include <cstdio>
#include <vector>
#include <bitset>
#define deb(n) fprintf(stderr,"%d ",(n));
#define DN 8200
using namespace std;

bitset<DN>viz;
vector<int> graf[DN];
int n,m,l[DN],r[DN],rez[3][DN];

bool cupleaza(int sursa) {
    if(viz[sursa]) return false;
    viz.flip(sursa);
    for(vector<int>::iterator i=graf[sursa].begin();i!=graf[sursa].end();++i) {
        if(!r[*i]) {
            l[sursa]=*i;
            r[*i]=sursa;
            return true;
        }
    }
    for(vector<int>::iterator i=graf[sursa].begin();i!=graf[sursa].end();++i) {
        if(cupleaza(r[*i])) {
            l[sursa]=*i;
            r[*i]=sursa;
            return true;
        }
    }
    return false;
}

void c(int sursa) {
    for(vector<int>::iterator it=graf[sursa].begin();it!=graf[sursa].end();++it)
        if(!rez[1][*it]) {
            rez[1][*it]=1;
            rez[0][r[*it]]=0;
            c(r[*it]);
        }
}

int main()
{
	int i,x,y,cont=0;
	bool ok=true;
	freopen ("felinare.in", "r", stdin);
    freopen ("felinare.out", "w", stdout);
	scanf("%d %d",&n,&m);
	for(i=1; i<=m;++i) {
	    scanf("%d %d",&x,&y);
	    graf[x].push_back(y);
	}
	while(ok) {
	    ok=false;
	    viz&=0;
	    for(i=1; i<=n;++i)
            if(!l[i])
                ok|=cupleaza(i);
	}
	for(i=1;i<=n;++i) if(l[i]) {
        rez[0][i]=1;
        ++cont;
    }
	for(i=1; i<=n;++i) if(!l[i]) c(i);
	printf("%d\n",2*n-cont);
	for(i=1;i<=n;++i) printf("%d\n",3-(rez[0][i]+(rez[1][i]<<1)));
	return 0;
}