#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define Nmax 8200

vector <int> graf[Nmax];
int n, m, ok, cMax;
int l[Nmax], r[Nmax], used[Nmax];
bool sl[Nmax], sr[Nmax];

void read(){
    int u, v;
    scanf("%i %i", &n, &m);
    for(int i = 1; i <= m; ++i){
        scanf("%i %i", &u, &v);
        graf[u].push_back(v);
    }
    fclose(stdin);
}

int cuplare(int node){
    int v;
    if(used[node]) return 0;
    used[node] = 1;
    for(int i = 0, size = graf[node].size(); i < size; ++i){
        v = graf[node][i];
        if(!r[v] || cuplare(r[v])){
            l[node] = v;
            r[v] = node;
            return 1;
        }
    }
    return 0;
}

void suport_minim(int n){
    int v;
    for(int i = 0, size = graf[n].size(); i < size; ++i){
        v = graf[n][i];
        if(!sr[v]){
            sr[v] = 1;
            sl[r[v]] = 0;
            suport_minim(r[v]);
        }
    }
}

void solve(){
    ok = 1;
    // hopcroft-karp
    while(ok){
        ok = 0;
        memset(used, 0, sizeof(used));
        for(int i = 1 ; i <= n; ++i){
            if(!l[i])
                if(cuplare(i)) ++cMax, ok = 1;
        }
    }
    // suport minim
    for(int i = 1; i <= n; ++i)
        if(l[i]) sl[i] = true;
    for(int i = 1; i <= n; ++i)
        if(!sl[i]) suport_minim(i);
}

void write(){
    printf("%i\n", 2*n-cMax);
    for(int i = 1; i <= n; ++i){
        if(!sl[i] && !sr[i]) printf("3\n");
        else if(!sl[i] && sr[i]) printf("1\n");
        else if(sl[i] && !sr[i]) printf("2\n");
        else printf("0\n");
    }
    fclose(stdout);
}

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

    read();
    solve();
    write();

    return 0;
}