#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;

const int nmax = 8200;

vector<int> gf[nmax];
bitset<nmax> viz, v_st, v_dr;
int n, m, st[nmax], dr[nmax];
int n_cup;
int sol;

void citeste(){

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

}

bool cupleaza(int nod){

    if (viz[nod] != 0) return 0;
    viz[nod]=1;
    for(unsigned i=0; i< gf[nod].size(); ++i){
        int vc = gf[nod][i];
        if (dr[vc]==0 || cupleaza( dr[vc] ) != 0){
            st[nod] = vc;
            dr[vc] = nod;
            v_st[nod] = 1;
            return 1;
        }
    }
    return 0;

}

void cuplaj_max(){

    int ok = 1;
    for(; ok; ){
        ok = 0;
        for (int i=1; i<=nmax; ++i) viz[i] = 0;
        for(int i=1; i<=n; ++i){
            if (st[i] == 0 && cupleaza(i)){
                ++n_cup;
                ok = 1;
            }
        }
    }

}

void calculeaza(int nod){

    for(unsigned i=0; i < gf[nod].size(); ++i){
        int vc = gf[nod][i];
        if (v_dr[vc] == 0){
            v_dr[vc] = 1;
            v_st[ dr[vc] ] = 0;
            calculeaza( dr[vc] );
        }
    }

}

void rezolva(){

    for(int i=1; i<=n; ++i){
        if (st[i]) v_st[i] = 1;
    }
    for(int i=1; i<=n; ++i)
        if (!st[i]) calculeaza(i);

}

void scrie(){

    printf("%d\n", (2*n) - n_cup);

    for(int i=1; i<=n; ++i){
        if (v_st[i] == 0 && v_dr[i] == 0) printf("3\n");
        else if (v_st[i] && v_dr[i]) printf("0\n");
        else if (v_st[i]) printf("2\n");
        else printf("1\n");

    }

}

int main(){

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

    citeste();
    cuplaj_max();
    rezolva();
    scrie();


    fclose(stdin);
    fclose(stdout);

    return 0;

}