#include <bits/stdc++.h>
using namespace std;

int n, m;
bool f[8200];
int l[8200], r[8200];
vector <int> v[8200];
inline bool cuplaj(int nod){
    if(f[nod]) return 0;
    f[nod] = 1;
    for(auto it : v[nod]){
        if(!r[it]){
            l[nod] = it;
            r[it] = nod;
            return 1;
        }

    }
    for(auto it : v[nod]){
        if(cuplaj(r[it])){
            l[nod] = it;
            r[it] = nod;
            return 1;
        }
    }
    return 0;
}
bool sl[8200], sr[8200];
inline void suport(int nod){
    for(auto it : v[nod]){
        if(!sr[it]){
            sr[it] = 1;
            sl[r[it]] = 0;
            suport(r[it]);
        }
    }
}
int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);

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

    do{
        bool ok = 0;
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= n ; ++i) if(!l[i]) ok |= cuplaj(i);
        if(ok == 0) break ;
    }while(1);

    int c = 0;
    for(int i = 1; i <= n ; ++i) if(l[i]) ++c, sl[i] = 1;
    printf("%d\n", n * 2 - c);

    for(int i = 1; i <= n ; ++i)
        if(!l[i]) suport(i);

    for(int i = 1; i <= n ; ++i){
        int val = 3;
        if(sl[i]) val -= 1;
        else if(sr[i]) val -= 2;
        printf("%d\n", val);
    }

    return 0;
}