#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 8191;
const int MMAX = 20000;

int N, M;
vector <int> g[NMAX + 5];

int minVertexCover;

bool d[NMAX + 5];
int l[NMAX + 5], r[NMAX + 5];

bool leftOn[NMAX + 5], rightOn[NMAX + 5];

void Read()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
    }
}

bool PairUp(int node)
{
    if(d[node] == true)
        return false;

    d[node] = true;

    for(auto it : g[node])
        if(!r[it])
        {
            minVertexCover++;

            l[node] = it, r[it] = node;
            return true;
        }

    for(auto it : g[node])
        if(PairUp(r[it]))
        {
            l[node] = it, r[it] = node;

            return true;
        }

    return false;
}

void Dfs(int node)
{
    for(auto it : g[node])
        if(!rightOn[it])
            {
                rightOn[it] = true;
                Dfs(r[it]);
            }
}

void Solve()
{
    bool ok;

    do
    {
        for(int i = 1; i <= N; i++)
            d[i] = false;

        ok = false;

        for(int i = 1; i <= N; i++)
            if(!l[i])
                ok |= PairUp(i);
    }
    while(ok == true);

    fout << 2 * N - minVertexCover << '\n';

    for(int i = 1; i <= N; i++)
        if(!l[i])
            Dfs(i);

    for(int i = 1; i <= N; i++)
        if(l[i] && !rightOn[l[i]])
            leftOn[i] = true;

    for(int i = 1; i <= N; i++)
        if(leftOn[i] == 0 && rightOn[i] == 0)
            fout << 3 << '\n';
        else if(leftOn[i] == 1 && rightOn[i] == 1)
            fout << 0 << '\n';
        else if(leftOn[i] == 1 && rightOn[i] == 0)
            fout << 2 << '\n';
        else
            fout << 1 << '\n';
}

int main()
{
    Read();

    Solve();

    return 0;
}