#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<vector<int> > Graph(8192);
int N, M, i, j, Sol[8192][3], ToRight[8192], ToLeft[8192], done, Mx;
bool Check[8192];
int Cuplaj(int i);
void Support(int i);
int Form(int i);
int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i) Graph[i].push_back(0);
    for(i=1; i<=M; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        ++Graph[x][0]; Graph[x].push_back(y);
    }
    do{
        done=0;
        for(i=1; i<=N; ++i) Check[i]=false;
        for(i=1; i<=N; ++i) if(ToRight[i]==0) if(Cuplaj(i)!=0) {done=1; ++Mx;}
    }while(done!=0);
    printf("%d\n", 2*N-Mx);
    for(i=1; i<=N; ++i) if(ToRight[i]!=0) Sol[i][1]=1;
    for(i=1; i<=N; ++i) if(Sol[i][1]==0) Support(i);
    for(i=1; i<=N; ++i) printf("%d\n", Form(i));
    return 0;
}
int Cuplaj(int i){
    if(Check[i]==true) return 0;
    Check[i]=true;
    int j;
    for(j=1; j<=Graph[i][0]; ++j) if(ToLeft[Graph[i][j]]==0){
        ToRight[i]=Graph[i][j];
        ToLeft[Graph[i][j]]=i;
        return 1;
    }
    for(j=1; j<=Graph[i][0]; ++j) if(Cuplaj(ToLeft[Graph[i][j]])!=0){
        ToRight[i]=Graph[i][j];
        ToLeft[Graph[i][j]]=i;
        return 1;
    }
    return 0;
}
void Support(int i){
    int j;
    for(j=1; j<=Graph[i][0]; ++j) if(Sol[Graph[i][j]][2]==0){
        Sol[Graph[i][j]][2]=1;
        Sol[ToLeft[Graph[i][j]]][1]=0;
        Support(ToLeft[Graph[i][j]]);
    }
    return;
}
int Form(int i){
    if(Sol[i][1]==0 && Sol[i][2]==0) return 3;
    if(Sol[i][1]==0 && Sol[i][2]==1) return 1;
    if(Sol[i][1]==1 && Sol[i][2]==0) return 2;
    if(Sol[i][1]==1 && Sol[i][2]==1) return 0;
}