#include <iostream>
#include <vector>
using namespace std;
#define maxn 8200
#define PB push_back

int N, M;
int L[maxn], R[maxn], U[maxn];
int SL[maxn], SR[maxn];
vector<int> G[maxn];

int pairUp(int nod) {
    if(U[nod]) return 0;
    U[nod] = 1;
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(!R[*it]) {
              L[nod] = *it;
              R[*it] = nod;
              return 1;
         }
    }
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(pairUp(R[*it])) {
              L[nod] = *it;
              R[*it] = nod;
              return 1;
         }
    }
    return 0;
}

void suport(int nod) {
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(!SR[*it]) {
              SR[*it] = 1;
              SL[ R[*it] ] = 0;
              suport(R[*it]);
         }
    }
}

int main() {
    FILE *f1=fopen("felinare.in", "r"), *f2=fopen("felinare.out", "w");
    int i, j, p, q;
    fscanf(f1, "%d %d\n", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d\n", &p, &q);
         G[p].PB(q);
    }
    int ok = 1;
    while(ok) {
         ok = 0;
         memset(U, 0, sizeof(U));
         for(i=1; i<=N; i++) {
              if(!L[i]) {
                   if(pairUp(i)) { ok = 1; }
              }
         }
    }
    for(i=1; i<=N; i++) {
         if(L[i]) {
              SL[i] = 1;
         }
    }
    for(i=1; i<=N; i++) {
         if(!L[i]) {
              suport(i);
         }
    }
    int sol = 0;
    for(i=1; i<=N; i++) {
         if(L[i]) sol++;
    }
    fprintf(f2, "%d\n", 2*N - sol);
    for(i=1; i<=N; i++) {
         int rasp;
         if(SL[i] && SR[i]) rasp = 0;
         if(!SL[i] && SR[i]) rasp = 1;
         if(SL[i] && !SR[i]) rasp = 2;
         if(!SL[i] && !SR[i]) rasp = 3;
         
         fprintf(f2, "%d\n", rasp);
    }
    fclose(f1); fclose(f2);
    return 0;
}