#include<bits/stdc++.h>
using namespace std;
#define NMAX 8200
#define MMAX 20100

int nxt[MMAX], last[NMAX], val[MMAX];
bool viz[NMAX], sup_st[NMAX], sup_dr[NMAX];
int cnt = 0;
int add(int a, int b){
    cnt++;
    val[cnt] = b;
    nxt[cnt] = last[a];
    last[a] = cnt;
}

int cupl_st[NMAX], cupl_dr[NMAX];
inline bool cuplaj(int a){
    int p, nod;
    if(viz[a])
        return 0;
    viz[a] = 1;
    p = last[a];
    while(p != 0){
        nod = val[p];
        if(cupl_dr[nod] == 0){
            cupl_st[a] = nod;
            cupl_dr[nod] = a;
            return 1;
        }
        p = nxt[p];
    }
    p = last[a];
    while(p != 0){
        nod = val[p];
        if(cuplaj(cupl_dr[nod])){
            cupl_st[a] = nod;
            cupl_dr[nod] = a;
            return 1;
        }
        p = nxt[p];
    }
    return 0;
}

void suport(int a){
    int nod;
    for(int p = last[a]; p; p = nxt[p]){
        nod = val[p];
        if(!sup_dr[nod]){
            sup_dr[nod] = 1;
            sup_st[cupl_dr[nod]] = 0;
            suport(cupl_dr[nod]);
        }
    }
    return;
}

int main(){
    FILE *in, *out;
    in = fopen("felinare.in", "r");
    out = fopen("felinare.out", "w");
    int n, m, x, y;
    fscanf(in, "%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        fscanf(in, "%d%d", &x, &y);
        add(x, y);
    }
    int done = 1;
    int rasp = 0;
    while(done){
        done = 0;
        memset(viz, 0, sizeof viz);
        for(int i = 1; i <= n; i++)
            if((!cupl_st[i]) && cuplaj(i)){
                done = 1;
                rasp++;
            }
    }
    fprintf(out, "%d\n", 2 * n - rasp);
    for(int i = 1; i <= n; i++)
        if(cupl_st[i])
            sup_st[i] = 1;
    for(int i = 1; i <= n; i++)
        if(!cupl_st[i])
            suport(i);
    int tmp;
    for(int i = 1; i <= n; i++){
        if(!sup_st[i]){
            if(!sup_dr[i])
                tmp = 3;
            else
                tmp = 1;
        }
        else{
            if(!sup_dr[i])
                tmp = 2;
            else
                tmp = 0;
        }
        fprintf(out, "%d\n", tmp);
    }
    return 0;

}