#include <fstream>
#include <vector>
#include <cstring>

#define MAX 8200

using namespace std;

int N, M, cnt;
int L[MAX], R[MAX], sL[MAX], sR[MAX];
vector<int> V[MAX];
bool viz[MAX];

void citire() {
    ifstream in("felinare.in");
    in>>N>>M;
    for(int i = 1, X, Y; i <= M; i++) {
        in>>X>>Y;
        V[X].push_back(Y);
    } in.close();
}

bool pairUp(int nod) {
    if(viz[nod]) return false;
    viz[nod] = true;
    for(vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
        if(!R[(*it)]) {
            L[nod] = (*it);
            R[(*it)] = nod;
            return true;
        }
    for(vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
        if(pairUp(R[(*it)])) {
            L[nod] = (*it);
            R[(*it)] = nod;
            return true;
        }
    return false;
}

void cuplaj() {
    for(int ok = 1; ok; ) {
        memset(viz, 0, sizeof(viz));
        ok = false;
        for(int i = 1; i <= N; i++)
            if(!L[i]) ok |= pairUp(i);
    }
}

void SpairUp(int nod) {
    for(vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
        if(!sR[(*it)]) {
            sR[(*it)] = true;
            sL[R[(*it)]] = false;
            SpairUp(R[(*it)]);
        }
}

void suport() {
    for(int i = 1; i <= N; i++) {
        sL[i] = (L[i] != 0);
        cnt += sL[i];
    }
    for(int i = 1; i <= N; i++)
        if(!sL[i]) SpairUp(i);
}

void afisare() {
    ofstream out("felinare.out");
    out<<2 * N - cnt<<"\n";
    for(int i = 1; i <= N; i++) {
        if(sL[i] && sR[i]) out<<"0\n";
        else if(!sL[i] && sR[i]) out<<"1\n";
        else if(!sR[i] && sL[i]) out<<"2\n";
        else out<<"3\n";
    } out.close();
}

int main() {
    citire();
    cuplaj();
    suport();
    afisare();
    return 0;
}