#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 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++)
        {
            int found = -1;

            for(auto it : g[i])
                if(l[i] == it && r[it] == i)
                    {
                        found = it;
                        break;
                    }

            if(found == -1)
                leftOn[i] = 1, rightOn[i] = 1;
            else
                leftOn[i] = 1;
        }

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

int main()
{
    Read();

    Solve();

    return 0;
}