#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <bitset>

using namespace std;

ifstream in("felinare.in");
ofstream out("felinare.out");

int n,m;
bitset<8195> U;
int ST[8195],DR[8195];
vector<int> L[8195];

bitset<8195> SUPST,SUPDR;

void read(){
    in>>n>>m;
    for(int x,y,i=1;i<=m;i++){
        in>>x>>y;
        L[x].push_back(y);
    }
}
bool pairup(int nod){
    if(U[nod])
        return 0;
    U[nod]=1;
    for(auto x : L[nod]){
        if(!ST[x]){
            ST[x]=nod;
            DR[nod]=x;
            return 1;
        }
    }
    for(auto x : L[nod]){
        if(pairup(ST[x])){
            ST[x]=nod;
            DR[nod]=x;
            return 1;
        }
    }
    return 0;
}
void support(int nod){
    for(auto x : L[nod])
        if(!SUPDR[x]){
            SUPDR[x]=1;
            SUPST[ST[x]]=0;
            support(x);
        }
}
void solve(){
    bool t=1;
    int maxi=0;
    while(t){
        t=0;
        U.reset();
        for(int i=1;i<=n;i++)
            if(!U[i]&&!DR[i])
                t=t||pairup(i);
    }
    for(int i=1;i<=n;i++)
        if(DR[i])
            maxi++;
    for(int i=1;i<=n;i++)
        if(ST[i])
            SUPST[i]=1;
    out<<2*n-maxi<<"\n";
    for(int i=1;i<=n;i++){
        int r=0;
        if(SUPST[i]==0)
            r++;
        if(SUPDR[i]==0)
            r+=2;
        out<<r<<"\n";
    }
}
int main(){
    read();
    solve();
    return 0;
}