#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int NMax = 8500;
vector <int> G[NMax + 5];

int L[NMax + 5], R[NMax + 5], N, M, Card;
bool Use[NMax + 5], Lviz[NMax + 5], Rviz[NMax + 5], ok;

bool Cuplaj(int Nod)
{
    if(Use[Nod]) return 0;

    Use[Nod] = 1;

    for(auto Vecin : G[Nod])
        if(!R[Vecin])
        {
            R[Vecin] = Nod;
            L[Nod] = Vecin;
            return 1;
        }

    for(auto Vecin : G[Nod])
        if(R[Vecin] && Cuplaj(R[Vecin]))
        {
            R[Vecin] = Nod;
            L[Nod] = Vecin;
            return 1;
        }
    return 0;
}

void Solve()
{
    do
    {
        ok = 0; memset(Use, 0, sizeof(Use));

        for(int i = 1; i <= N; i++)
            if(L[i] == 0)
                ok |= Cuplaj(i);
    }
    while(ok);
}

void PairUp(int Nod)
{
    for(auto Vecin : G[Nod])
        if(!Rviz[Vecin])
        {
            Rviz[Vecin] = 1; Lviz[R[Vecin]] = 0;
            PairUp(R[Vecin]);
        }
}

void Suport()
{
    for(int i = 1; i <= N; i++)
        Lviz[i] = (L[i] != 0), Card += (L[i] != 0);

    for(int i = 1; i <= N; i++)
        if(!Lviz[i])
            PairUp(i);
}

int main()
{
    fin >> N >> M;

    while(M--)
    {
        int x, y;
        fin >> x >> y;

        G[x].push_back(y);
    }
    Solve();
    Suport();

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

    for(int i = 1; i <= N; i++)
        fout << (1 ^ Lviz[i] + 2 * (1 ^ Rviz[i])) << '\n';

    fin.close();
    fout.close();

    return 0;
}