#include <cstring>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

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


const int Maxn = 10003;


vector <int> G[Maxn];

int n, m, nr_e;
int l[Maxn], r[Maxn], u[Maxn];


int pairup(const int a)
{
    if (u[a])  return 0;
    u[a] = 1;
    for ( auto i : G[a])
        if (!r[i])
        {
            l[a] = i;
            r[i] = a;
            return 1;
        }
    for ( auto i : G[a])
        if (pairup(r[i]))
        {
            l[a] = i;
            r[i] = a;
            return 1;
        }
    return 0;
}

int main()
{



    fin >> n >> nr_e;
    m = n;
    for (; nr_e --; )
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }
    for (int k = 1; k; )
    {
        k = 0;
        memset(u, 0, sizeof(u));
        for (int i = 1; i <= n; i++)
            if (!l[i])
                k |= pairup(i);
    }
    int cuplaj = 0;
    for (int i = 1; i <= n; i++)
        if ( l[i] )
            cuplaj++;
    fout << n * 2 - cuplaj << '\n';
    for (int i = 1; i <= n; i++)
    {
        if ( l[i]  )
            fout << 2 << '\n';
        else
            fout << 3 << '\n';

    }
    return 0;
}