#include<cstdio>
#include<vector>
#define N 8191
using namespace std;

vector<int> vecin[N+1];

int left[N+1];
int right[N+1];

int viz[N+1];
int k;

bool stinsL[N+1];
bool stinsR[N+1];

bool pairUp(int nod){
    if (viz[nod]==k) return false;

    viz[nod]=k;

    for(int i=0;i<vecin[nod].size();i++){
        int now=vecin[nod][i];

        if (left[now]==0 ||pairUp(left[now])==true){
            left[now]=nod;
            right[nod]=now;
            return true;
        }
    }

    return false;
}

void aprinde(int nod){
    int i;

    for(i=0;i<vecin[nod].size();i++){
        int now=vecin[nod][i];

        if (stinsR[now]==false){
            stinsR[now]=true;
            stinsL[left[now]]=false;
            aprinde(left[now]);
        }
    }
}

int main(){
    freopen ("felinare.in","r",stdin);
    freopen ("felinare.out","w",stdout);
    int n,m,i;

    scanf ("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        int x,y;
        scanf ("%d%d",&x,&y);
        vecin[x].push_back(y);
    }

    int cnt=0;
    for(i=1;i<=n;i++){
        k=i;
        cnt+=pairUp(i);
    }

    printf ("%d\n",2*n-cnt);

    for(i=1;i<=n;i++)
        if (right[i]!=0) stinsL[i]=true;

    for(i=1;i<=n;i++)
        if (right[i]==0) aprinde(i);

    for(i=1;i<=n;i++){
        int x=0;
        if (stinsL[i]==false) x+=1;
        if (stinsR[i]==false) x+=2;

        printf ("%d\n",x);
    }

    return 0;
}