#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define FILEIN "felinare.in"
#define FILEOUT "felinare.out"

const int NMAX = 8200;

int N, M;
vector<int> A[NMAX];
int L[NMAX], R[NMAX];
bool SL[NMAX], SR[NMAX];
bool mark[NMAX];
int sol[NMAX];

bool cupleaza (int node) {
    if (mark[node]) return false;
    mark[node] = true;
    for ( int i = 0; i < A[node].size(); i++) {
        int y = A[node][i];
        if (!R[y]) {
            R[y] = node;
            L[node] = y;
            return true;
        }
    }
    for ( int i = 0; i < A[node].size(); i++) {
        int y = A[node][i];
        if (cupleaza(R[y])) {
            R[y] = node;
            L[node] = y;
            return true;
        }
    }
    return false;
}

void support (int node) {
    for(int i = 0; i < A[node].size(); i++){
        if(!SR[A[node][i]])
        {
            SR[A[node][i]] = true;
            SL[R[A[node][i]]] = false;
            support(R[A[node][i]]);
        }
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

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

    bool tmp = 1;
    while(tmp) {
        memset(mark, 0, sizeof(mark));
        tmp = false;
        for ( int i = 1; i <= N; i++) {
            if (!L[i])
                if(cupleaza(i))
                    tmp = true;
        }
    }

    for ( int i = 1; i <= N; i++) {
        SL[i] = (L[i] > 0);
    }

    for ( int i = 1; i <= N; i++) {
        if (!L[i])
            support(i);
    }
    int rez = 0;
    for ( int i = 1; i <= N; i++) {
        if (!SL[i]) {
            rez++;
            sol[i] += 1;
        }
        if (!SR[i]) {
            rez++;
            sol[i] += 2;
        }
    }
    printf("%d\n", rez);
    for ( int i = 1; i <= N; i++) {
        printf("%d\n", sol[i]);
    }

    return 0;
}