#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 82e2;

int N, M, X, Y;

int L[NMAX], R[NMAX];

bool Marked[NMAX];

vector < int > G[NMAX];

vector < int > Edges_Left[NMAX], Edges_Right[NMAX];

bool Sel_Left[NMAX], Sel_Right[NMAX];

bool Minim_Left[NMAX], Minim_Right[NMAX];

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> X >> Y;

        G[X].push_back(Y);
    }

    return;
}

static inline bool Cupleaza (int Node)
{
    Marked[Node] = 1;

    for(auto it : G[Node])
        if(!R[it])
        {
            L[Node] = it;

            R[it] = Node;

            return true;
        }

    for(auto it : G[Node])
        if(!Marked[R[it]] && Cupleaza(R[it]))
        {
            L[Node] = it;

            R[it] = Node;

            return true;
        }

    return false;
}

static inline void Max_Match ()
{
    bool done = 1;

    while(done)
    {
        done = 0;

        for(int i = 1; i <= N; ++i)
            Marked[i] = false;

        for(int i = 1; i <= N; ++i)
            if(!Marked[i] && !L[i])
                done |= Cupleaza(i);
    }

    int cnt = 0;

    for(int i = 1; i <= N; ++i)
        if(L[i])
            ++cnt;

    g << 2 * N - cnt << '\n';

    return;
}

static inline void DFS (int Node, char ch)
{
    if(ch == 'L')
    {
        Sel_Left[Node] = true;

        for(auto it : Edges_Left[Node])
            if(!Sel_Right[it])
                DFS(it, 'R');

        return;
    }

    Sel_Right[Node] = true;

    for(auto it : Edges_Right[Node])
        if(!Sel_Left[it])
            DFS(it, 'L');

    return;
}

static inline void MVC ()
{
    for(int i = 1; i <= N; ++i)
    {
        if(L[i])
            Edges_Right[L[i]].push_back(i);

        for(auto it : G[i])
            if(it != L[i])
                Edges_Left[i].push_back(it);
    }

    for(int i = 1; i <= N; ++i)
        if(!L[i] && !Sel_Left[i])
            DFS(i, 'L');

    for(int i = 1; i <= N; ++i)
        if(L[i] && !Sel_Left[i])
            Minim_Left[i] = true;

    for(int i = 1; i <= N; ++i)
        if(R[i] && Sel_Right[i])
            Minim_Right[i] = true;

    return;
}

static inline void MIS ()
{
    for(int i = 1; i <= N; ++i)
    {
        bool P1 = !Minim_Left[i];
        bool P2 = !Minim_Right[i];

        if(P1 && P2)
        {
            g << 3 << '\n';

            continue;
        }

        if(!P1 && !P2)
        {
            g << 0 << '\n';

            continue;
        }

        if(P1)
            g << 1;
        else
            g << 2;

        g << '\n';
    }

    return;
}

int main()
{
    Read();

    Max_Match();

    MVC();

    MIS();

    return 0;
}