#include <cstdio>
#include <algorithm>
#include <bitset>
#include <vector>

#define DIM 16384
using namespace std;

int nrNodes, nrEdges, node1, node2;

int Left[DIM], Right[DIM], LeftEdges[DIM], RightEdges[DIM];
bitset <DIM> Marked; vector <int> Edges[DIM];

bool VertexCover (int node)
{
    if (Marked[node]) return 0; Marked[node] = 1;
    vector <int> :: iterator it;

    for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
    {
        int nextNode = *it;

        if (!Right[nextNode])
        {
            Left[node] = nextNode;
            Right[nextNode] = node;
            LeftEdges[node] = 1;

            return 1;
        }
    }

    for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
    {
        int nextNode = *it;

        if (VertexCover(Right[nextNode]))
        {
            Left[node] = nextNode;
            Right[nextNode] = node;
            LeftEdges[node] = 1;

            return 1;
        }
    }

    return 0;
}

void DFS (int node)
{
    vector <int> :: iterator it;
    for (it = Edges[node].begin(); it != Edges[node].end(); it ++)
    {
        int nextNode = *it;

        if (!RightEdges[nextNode])
        {
            RightEdges[nextNode] = 1;
            LeftEdges[Right[nextNode]] = 0;

            DFS (Right[nextNode]);
        }
    }

    return;
}

int main ()
{
    freopen ("felinare.in" , "r", stdin );
    freopen ("felinare.out", "w", stdout);

    scanf ("%d %d", &nrNodes, &nrEdges);

    for (int i = 1; i <= nrEdges; i ++)
    {
        scanf ("%d %d", &node1, &node2);
        Edges[node1].push_back(node2 + nrNodes);
    }

    int ok;
    do {
        ok = 0; Marked.reset();

        for (int i = 1; i <= nrNodes; i ++)
            if (!Left[i] && VertexCover(i))
                ok = 1;

    } while (ok);

    int sol = 0;
    for (int i = 1; i <= nrNodes; i ++)
        sol += (Left[i] != 0) ? 1 : 0;

    sol = nrNodes * 2 - sol;
    printf ("%d\n", sol);

    for (int i = 1; i <= nrNodes; i ++)
        if (!LeftEdges[i])
            DFS (i);

    int edges = 0;
    for (int i = 1; i <= nrNodes; i ++)
    {
        if ( LeftEdges[i] &&  RightEdges[i]) edges = 0; else
        if (!LeftEdges[i] &&  RightEdges[i]) edges = 1; else
        if ( LeftEdges[i] && !RightEdges[i]) edges = 2; else
        if (!LeftEdges[i] && !RightEdges[i]) edges = 3; else
            printf ("What da hek is the answer then ??");

        printf ("%d\n", edges);
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}