#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>

#define NMAX 8193

using namespace std;
typedef vector<int>::iterator iter;

ifstream fin ("felinare.in");
ofstream fout ("felinare.out");

int n, m, l[NMAX], r[NMAX], sl[NMAX], sr[NMAX], e;
vector<int> G[NMAX];
bitset<NMAX> viz;

void citire()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }
}

bool match(int nod)
{
    if (viz[nod])
        return false;
    viz[nod] = true;

    for (iter it = G[nod].begin(); it != G[nod].end(); it++)
    {
        if (r[*it] == 0)
        {
            l[nod] = *it;
            r[*it] = nod;
            return true;
        }
        if (match(r[*it]) == true)
        {
            l[nod] = *it;
            r[*it] = nod;
            return true;
        }
    }

    return false;
}

void suport(int nod)
{
    for (auto elem : G[nod])
    {
        if (sr[elem] == 0)
        {
            sr[elem] = 1;
            sl[r[elem]] = 0;

            suport(r[elem]);
        }
    }
}

int main()
{
    citire();

    bool ok = true;
    while (ok)
    {
        ok = false;
        viz.reset();

        for (int i = 1; i <= n; i++)
            if (l[i] == 0)
                ok |= match(i);
    }

    int cuplaj = 0;
    for (int i = 1; i <= n; i++)
        if (l[i]) cuplaj++;

    for (int i = 1; i <= n; i++)
        if (l[i]) sl[i] = 1;

    for (int i = 1; i <= n; i++)
        if (!l[i]) suport(i);

    int sol = 0;
    for (int i = 1; i <= n; i++)
    {
        if (sl[i] == 0) sol++;
        if (sr[i] == 0) sol++;
    }

    fout << sol << "\n";
    for (int i = 1; i <= n; i++)
    {
        if (sl[i] && sr[i]) fout << 0 << "\n";
        if (sl[i] == 0 && sr[i]) fout << 1 << "\n";
        if (sl[i] && sr[i] == 0) fout << 2 << "\n";
        if (sl[i] == 0 && sr[i] == 0) fout << 3 << "\n";
    }
    return 0;
}