#include <bits/stdc++.h>
using namespace std;
int noduri , muchii,st[8195], dr[8195], stt[8195], drr[8195];
bool sel[8195];
vector <int> g[8195];
inline int match(int nod)
{
    if (sel[nod] == true)
        return 0;
    sel[nod] = true;
    for (auto &it : g[nod])
        if (!dr[it])
        {
            st[nod] = it;
            dr[it] = nod;
            return 1;
        }
    for (auto &it : g[nod])
        if (match(dr[it]))
        {
            st[nod] = it;
            dr[it] = nod;
            return 1;
        }
    return 0;
}
inline void ver_cover(int nod)
{
    for (auto &it : g[nod])
        if (!drr[it])
        {
            drr[it] = true;
            stt[dr[it]] = false;
            ver_cover(dr[it]);
        }
}
int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);

    scanf("%d %d\n", &noduri , &muchii);
    for (int i = 1; i<=muchii; ++i)
    {
        int x , y;
        scanf("%d %d\n", &x, &y);
        g[x].push_back(y);
    }
    int untill = 1;
    while (untill)
    {
        untill = 0;
        memset(sel, false, sizeof(sel));
        for (int i = 1; i<=noduri; ++i)
            if (!st[i])
                untill |= match(i);
    }
    int sol = 2 * noduri;
    for (int i = 1; i<=noduri; ++i)
        stt[i] = (st[i] != 0) , sol -= (st[i] != 0);
    for (int i = 1; i<=noduri; ++i)
        if (!stt[i])
            ver_cover(i);
    printf("%d\n", sol);
    for (int i = 1; i<=noduri; ++i)
        printf("%d\n", (stt[i] == false) + 2 * (drr[i] == false));
    return 0;
}