#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define dim 8192

int n,m;
bool seen[dim*2+4];
vector<int> Adj[dim*2+4];
int L[dim*2+4],R[dim*2+4];
bool used[dim*2+4];

bool cuplaj(int x)
{
    if(seen[x]) return
        false;
    seen[x] = 1;

    for(auto p: Adj[x]) {
        if(!L[p] || cuplaj(L[p])) {
            R[x] = p;
            L[p] = x;
            return true;
        }
    }

    return false;
}

void min_vertex_cover(int x)
{
    for(auto p: Adj[x]) {
        if(!used[p]) {
            used[p] = 1;
            used[L[p]] = 0;
            min_vertex_cover(L[p]);
        }
    }
}

int main()
{
    ifstream fin("felinare.in");
    ofstream fout("felinare.out");

    fin >> n >> m;

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

    int Sol = 2*n;
    bool ok = true;

    while(ok) {
        ok = false;
        for(int i = 1; i <= 2*n; i++)
            seen[i] = false;

        for(int i = 1; i <= n; i++) {
            if(!R[i] && cuplaj(i)) {
                --Sol;
                ok = true;
            }
        }
    }

    for(int i = 1; i <= n; i++)
        if(R[i])
            used[i] = 1;

    for(int i = 1; i <= n; i++)
        if(!used[i])
            min_vertex_cover(i);

    fout << Sol << "\n";

    int type;
    for(int i = 1; i <= n; i++) {
        if(!used[i] && !used[i+n])
            type = 3;
        else if(!used[i])
            type = 1;
        else if(!used[i+n])
            type = 2;
        else
            type = 0;
        fout << type << "\n";
    }
}