#include <fstream>
#define fisier "felinare"
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const int N = 8192, M = N;
int L[M], R[N], s;
#include <vector>
std::vector<int> V[N];
#include <bitset>
std::bitset<N> E, S, D;
bool gasit(int);
bool cauta(int l, bool sat)
{
    for (int r: V[l])
        if (sat? gasit(L[r]): not L[r])
        {
            L[r] = l; R[l] = r;
            if (not sat) s++;
            return D[l] = true;
        }
    return false;
}
bool gasit(int l)
{
    if (E[l])
        return false;
    E[l] = true;
    return cauta(l, false) or cauta(l, true);
}
void dfs(int l)
{
    for (int r: V[l])
        if (not S[r])
        {
            S[r] = true;
            D[L[r]] = false;
            dfs(L[r]);
        }
}
int main()
{
    int n, m;
    in >> n >> m;
    while (m--)
    {
        int l, r;
        in >> l >> r;
        V[l].push_back(r);
    }
    bool cup;
    do
    {
        E = cup = false;
        for (int l = 1; l <= n; l++)
            cup |= not R[l] and gasit(l);
    }
    while (cup);
    out << 2 * n - s << '\n';
    for (int l = 1; l <= n; l++)
        if (not D[l])
            dfs(l);
    for (int l = 1; l <= n; l++)
        out << 2 * not S[l] + not D[l] << '\n';
}