#include<iostream>
#include<fstream>
#include<vector>
#include<iterator>

using namespace std;

ifstream f("felinare.in");
ofstream g("felinare.out");

int L[8200], R[8200];
int SL[8200], SR[8200], use[8200];
vector <int> G[8200];
int n, m, cupl;

void citire()
{
    int i, x, y;

    f>>n>>m;
    for(i=1; i<=m; i++){
        f>>x>>y;
        G[x].push_back(y);
    }
}

bool pairup(int nod)
{
    vector <int>::iterator it;
    if(use[nod])
        return false;
    use[nod] = 1;

    for(it = G[nod].begin(); it != G[nod].end(); it++)
        if(R[*it] == 0){
            L[nod] = *it;
            R[*it] = nod;
            return true;
        }

    for(it = G[nod].begin(); it != G[nod].end(); it++)
        if(pairup(R[*it])){
            L[nod] = *it;
            R[*it] = nod;
            return true;
        }

    return false;
}

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

void afiseaza(int i)
{
    if(!SL[i] && !SR[i]){
        g<<3<<"\n";
        return;
    }
    if(SL[i] && SR[i]){
        g<<0<<"\n";
        return;
    }
    if(!SR[i]){
        g<<2<<"\n";
        return;
    }

    g<<1<<"\n";
}

void rez()
{
    int i, ok = 1;

    while(ok){
        ok = 0;
        for(i=1; i<=n; i++)
            use[i] = 0;

        for(i=1; i<=n; i++){
            if(L[i] == 0)
                if(pairup(i)){
                    ok = 1;
                    cupl++;
                }
        }
    }

    for(i=1; i<=n; i++)
        if(L[i])
            SL[i] = 1;

    for(i=1; i<=n; i++)
        if(!SL[i])
            support(i);

    g<<(2*n - cupl)<<"\n";

    for(i=1; i<=n; i++)
        afiseaza(i);
}

int main()
{
    citire();
    rez();
    return 0;
}