#include <fstream>
#include <vector>
#define MAXN 8200
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");

int n,m,x,y,l[MAXN],r[MAXN],cuplaj,sol;
bool gata,uz[MAXN],sl[MAXN],sr[MAXN];
vector<int> GL[MAXN],GR[MAXN];

bool cupleaza(int p);
void completeaza(int p);

int main()
{
    int i,j;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        GL[x].push_back(y);
        GR[y].push_back(x);}
    while(!gata){
        gata=1;
        for(i=1;i<=n;i++)
            uz[i]=0;
        for(i=1;i<=n;i++)
            if(!l[i]&&cupleaza(i)){
                gata=0;
                cuplaj++;}}
    sol=2*n-cuplaj;
    g<<sol<<'\n';
    for(i=1;i<=n;i++)
        if(l[i])
            sl[i]=1;
    for(i=1;i<=n;i++)
        if(!l[i])
            completeaza(i);
    for(i=1;i<=n;i++){
        if(sl[i]){
            if(sr[i])
                g<<"0\n";
            else
                g<<"2\n";}
        else{
            if(sr[i])
                g<<"1\n";
            else
                g<<"3\n";}}
    f.close();
    g.close();
    return 0;
}

bool cupleaza(int p){
    int i;
    if(uz[p])
        return 0;
    uz[p]=1;
    for(i=0;i<GL[p].size();i++){
        x=GL[p][i];
        if(!r[x]){
            l[p]=x;
            r[x]=p;
            return 1;}}
    for(i=0;i<GL[p].size();i++){
        x=GL[p][i];
        if(cupleaza(r[x])){
            x=GL[p][i];
            l[p]=x;
            r[x]=p;
            return 1;}}
    return 0;}

void completeaza(int p){
    int i;
    for(i=0;i<GL[p].size();i++){
        x=GL[p][i];
        if(!sr[x]){
            sr[x]=1;
            sl[r[x]]=0;
            completeaza(r[x]);}}}