#include <fstream>
#include <vector>
using namespace std;

#define NMax 8200

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

int n,m;
vector<int> v[NMax];
bool soll[NMax],solr[NMax];

bool viz[NMax];
int l[NMax],r[NMax];

int pairup(int x)
{
    if(viz[x]) return 0;

    viz[x] = true;

    for(int i=0;i<v[x].size();++i) if(!r[v[x][i]])
    {
        l[x] = v[x][i];
        r[v[x][i]] = x;
        return 1;
    }

    for(int i=0;i<v[x].size();++i) if(pairup(r[v[x][i]]))
    {
        l[x] = v[x][i];
        r[v[x][i]] = x;
        return 1;
    }

    return 0;
}

void check(int x) // doar pentru noduri care nu sunt in solutie
{
    for(int i=0;i<v[x].size();++i) if(!solr[v[x][i]]) // pentru fiecare nod vecin care nu e in solutie
    {
        solr[v[x][i]] = true; // il bagam in solutie (dreapta)
        soll[r[v[x][i]]] = false; // si scoatem pe cel cu care e cuplat (din stanga)
        check(r[v[x][i]]);
    }
}

int main()
{
    int i,a,b;

    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>a>>b;
        v[a].push_back(b);
    }

    bool change = 1;
    while(change)
    {
        change = 0;
        for(i=1;i<=n;++i) viz[i] = false;
        for(i=1;i<=n;++i) if(!l[i]) change |= pairup(i);
    }

    int cuplaje = 0;
    for(i=1;i<=n;++i) if(l[i]) soll[i] = true, ++cuplaje;
    //daca e cuplat, il bag in solutie (stanga)

    for(i=1;i<=n;++i) if(!l[i]) check(i);
    //daca nu e cuplat, verific daca pot sa-l bag in solutie

    g<<2*n-cuplaje<<"\n";

    for(i=1;i<=n;++i)
    {
        if(soll[i] && solr[i]) g<<"0\n";
        else if(soll[i]) g<<"2\n";
        else if(solr[i]) g<<"1\n";
        else g<<"3\n";
    }

    f.close();
    g.close();
    return 0;
}