#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(!SUPST[x]){
            SUPST[x]=1;
            SUPDR[ST[x]]=0;
            support(ST[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++;
        if(DR[i])
            SUPDR[i]=1;
    }
    out<<2*n-maxi<<"\n";

    for(int i=1;i<=n;i++)
        if(!SUPDR[i])
            support(i);

    for(int i=1;i<=n;i++){
        out<<1-SUPDR[i]+2*(1-SUPST[i])<<"\n";
    }
}
int main(){
    read();
    solve();
    return 0;
}