#include <fstream>
#include <vector>
#include <cstring>
#define NM 20010

using namespace std;

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

int N, M;
vector<int> G[NM];
int L[NM], R[NM];
int SL[NM], SR[NM];
bool C[NM];
int Matched;

void Read ()
{
    f >> N >> M;
    for (int i=1; i<=M; i++)
    {
        int a, b;
        f >> a >> b;
        G[a].push_back(b);
    }

    f.close();
}

bool PairUp (int Node)
{
    if (C[Node]) return 0;
    C[Node]=1;

    for (vector<int>::iterator it=G[Node].begin(); it!=G[Node].end(); ++it)
        if (!R[*it])
        {
            R[*it]=Node;
            L[Node]=*it;
            return 1;
        }

    for (vector<int>::iterator it=G[Node].begin(); it!=G[Node].end(); ++it)
        if (PairUp(R[*it]))
        {
            R[*it]=Node;
            L[Node]=*it;
            return 1;
        }

    return 0;
}

void DoMatching ()
{
    bool ok=1;
    while (ok)
    {
        ok=0;
        memset(C, 0, sizeof(C));
        for (int i=1; i<=N; i++)
            if (!L[i])
                ok|=PairUp(i);
    }

    for (int i=1; i<=N; i++)
        Matched+=(L[i]!=0);
}

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

void DoMinVertexCover ()
{
    for (int i=1; i<=N; i++)
        SL[i]=(L[i]!=0);

    for (int i=1; i<=N; i++)
        if (!L[i])
            Cover(i);
}

void Print ()
{
    g << 2*N-Matched << '\n';

    for (int i=1; i<=N; i++)
    {
        if (SL[i]==1 && SR[i]==1) g << 0 << '\n';
        if (SL[i]==0 && SR[i]==1) g << 1 << '\n';
        if (SL[i]==1 && SR[i]==0) g << 2 << '\n';
        if (SL[i]==0 && SR[i]==0) g << 3 << '\n';
    }

    g.close();
}

int main ()
{
    Read();
    DoMatching();
    DoMinVertexCover();
    Print();

    return 0;
}