#include <bits/stdc++.h>

using namespace std;
ifstream f ("felinare.in");
ofstream g ("felinare.out");

constexpr int NMAX = 8200;
vector <int> G[NMAX];
int l[NMAX], r[NMAX];
bool lin[NMAX], col[NMAX];
int n, m, cuplaj;
bool marked[NMAX];

bool cupleaza (int ind)
{
    marked[ind]=1;
    for (auto it : G[ind])
    {
        if (!r[it])
        {
            l[ind]=it;
            r[it]=ind;
            return true;
        }
    }

    for (auto it : G[ind])
    {
        if (!marked[r[it]] && cupleaza(r[it]))
        {
            l[ind]=it;
            r[it]=ind;
            return true;
        }
    }

    return false;
}

void dfs (int nod)
{
    for (auto it : G[nod])
    {
        if (!col[it])
        {
            col[it]=1;
            lin[r[it]]=0;
            dfs(r[it]);
        }
    }
}

int main()
{
    f >> n >> m;

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

    bool done = 1;

    while (done)
    {
        done = 0;
        for (int i=1; i<=n; ++i) marked[i]=0;
        for (int i=1; i<=n; ++i)
            if (!marked[i] && !l[i])
                done |= cupleaza(i);
    }

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

    g << 2 * n - cuplaj << '\n';

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

    for (int i=1; i<=n; ++i)
        if (lin[i] == 0) dfs(i);

    for (int i=1; i<=n; ++i)
    {
        if (lin[i] == 0 && col[i] == 0) g << "3\n";
        if (lin[i] == 1 && col[i] == 0) g << "2\n";
        if (lin[i] == 0 && col[i] == 1) g << "1\n";
        if (lin[i] == 1 && col[i] == 1) g << "0\n";
    }
    return 0;
}