using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
ifstream fin("felinare.in");
ofstream fout("felinare.out");

#define NMAX 8192
#define pb push_back

int n, m;
vector<int> G[2*NMAX];
bool uz[2*NMAX];
int st[2*NMAX], dr[2*NMAX];
int ansL[2*NMAX], ansR[2*NMAX];

bool cuplaj(int nod) {
    uz[nod] = 1;
    for (auto it: G[nod]) {
        if (!st[it]) {
            st[it] = nod;
            dr[nod] = it;
            return 1;
        }
    }
    
    for (auto it: G[nod]) {
        if (!uz[st[it]] && cuplaj(st[it])) {
            dr[nod] = it;
            st[it] = nod;
            return 1;
        }
    }
    return 0;
}

void dfs(int nod) {
    for (auto it: G[nod]) {
        if (!ansR[it]) {
            ansL[st[it]] = 0;
            ansR[it] = 1;
            dfs(st[it]);
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i<=m; i++) {
        int a, b;
        fin >> a >> b;
        G[a].pb(b+n);
        G[b+n].pb(a);
    }

    bool ok = 1;
    while (ok) {
        ok = 0;
        for (int i = 1; i<=2*n; i++) uz[i] = 0;
        for (int i = 1; i<=n; i++) {
            if (!uz[i] && !dr[i]) {
                ok |= cuplaj(i);
            }
        }
    }
  
    int nrfel = 0;
    for (int i = 1; i<=n; i++) {
        if (dr[i]) {
            ansL[i] = 1;
        }
    }
    
    for (int i = 1; i<=n; i++) {
        if (!dr[i]) {
            dfs(i);
        }
    }
    
    ///iau tot restul, pentru ca total - min vertex cover = nr felinare maxim
    for (int i = 1; i<=n; i++) {
        if (!ansL[i]) {
            nrfel++;
        }
    }
    
    for (int i = n+1; i<=2*n; i++) {
        if (!ansR[i]) {
            nrfel++;
        }
    }
    
    fout << nrfel << "\n";
    
    for (int i = 1; i<=n; i++) {
        if (ansL[i] && ansR[i+n]) fout << "0\n";
        else if (!ansL[i] && ansR[i+n]) fout << "1\n";
        else if (ansL[i] && !ansR[i+n]) fout << "2\n";
        else fout << "3\n";
    }
    
    return 0;
}