#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

vector<int> g[8200];
bool vis[8200];
int l[8200], r[8200];
bool sr[8200], sl[8200];

bool PairUp(int node)
{
    if (vis[node])
        return false;
    vis[node] = true;
    for (unsigned i = 0; i < g[node].size(); i++)
        if (r[g[node][i]] == 0 || PairUp(r[g[node][i]]))
        {
            l[node] = g[node][i];
            r[g[node][i]] = node;
            return true;
        }
    return false;
}

void support (int x)
{
    for (int i = 0; i < g[x].size(); i++)
        if (!sr[g[x][i]])
        {
            sr[g[x][i]] = 1;
            sl[r[g[x][i]]] = 0;
            support(r[g[x][i]]);
        }
}

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

    int n, m;
    scanf("%d%d", &n, &m);
    for (int x, y; m; m--)
    {
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
    }

    int sol = 0;
    bool ok = true;
    while (ok)
    {
        ok = false;
        memset(vis, false, sizeof(vis));
        for (int i = 1; i <= n; i++)
            if (!l[i])
                if (PairUp(i))
                {
                    sol++;
                    ok = true;
                }
    }

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

    printf("%d\n", 2*n - sol);
    for (int i = 1; i <= n; i++)
    {
        int answer = 3;
        if (sl[i])
            answer--;
        if (sr[i])
            answer -= 2;
        printf("%d\n", answer);
    }

    return 0;
}