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

using namespace std;

vector <int> eg[10010];
int n, m;
int le[10010], ri[10010], val[20010];
bool ap[20010];

int cupleaza (int nod)
{
    if (ap[nod]) return 0;
    ap[nod] = true;

    for (auto &it : eg[nod])
        if (!ri[it])
        {
            le[nod] = it;
            ri[it] = nod;
            return 1;
        }

    for (auto &it : eg[nod])
        if (cupleaza (ri[it]))
        {
            le[nod] = it;
            ri[it] = nod;
            return 1;
        }

    return 0;
}

void cover (int nod)
{
    if (ap[nod]) return;

    for (auto &it : eg[nod])
        if (!ap[it + n])
        {
            ap[ri[it]] = false;
            ap[it + n] = true;
            cover (ri[it]);
        }
}

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

    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        scanf ("%d %d", &a, &b);

        eg[a].push_back (b);
    }

    bool OK = true;
    for (; OK;)
    {
        OK = false;

        for (int i = 1; i <= n; ++i)
            ap[i] = false;

        for (int i = 1; i <= n; ++i)
            if (!le[i])
                if (cupleaza (i)) OK = true;
    }

    for (int i = 1; i <= n; ++i)
    {
        ap[i] = false;
        if (le[i]) ap[i] = true;
    }

    for (int i = 1; i <= n; ++i)
        if (!ap[i]) cover (i);

    int nr = 0;

    for (int i = 1; i <= n; ++i)
    {
        val[i] = (!ap[i]) + 2 * (!ap[i + n]);
        nr += (!ap[i]) + (!ap[i + n]);
    }

    printf ("%d\n", nr);

    for (int i = 1; i <= n; ++i)
        printf ("%d\n", val[i]);

    return 0;
}