/*
    graf bipartit cu muchiile reprezentand drumuri si nodurile felinare
    n noduri in stanga felinarele de plecare si n noduri in dreapta felinarele de sosire
    minimum vertex cover pentru a afla felinarele ce trebuie stinse
*/

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int N_MAX = 8200;

int n;
vector<int> vecin[N_MAX]; //vecinul din a doua multime a unui nod din prima multime
int cuplat[N_MAX]; //nodul din prima multime cu care este cuplat un nod din a doua multime sau 0 daca nu este cuplat
int l_cuplaj=0;
bool vizitat[N_MAX];
bool marcat_a[N_MAX] = {false}; //pentru nodurile din stanga respectiv dreapta daca fac sau nu parte din minimum vertex cover
bool marcat_b[N_MAX] = {false};

void citeste()
{
    int m,a,b;
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d",&a,&b);
        vecin[a].push_back(b);
    }
}

int cuplare(int nod) //intoarce 0 sau 1 daca s-a cuplat vre-un nod sau nu (fara cele cuplate recursiv)
{
    int dest;
    if (vizitat[nod])
        return 0;
    vizitat[nod] = true;
    for (unsigned int i = 0; i < vecin[nod].size(); ++i)
    {
        dest = vecin[nod][i];
        if (!cuplat[dest] || cuplare(dest))
        {
            cuplat[dest] = nod;
            return 1;
        }
    }
    return 0;
}

void cuplaj()
{
    for (int i = 1; i <= n; ++i)
    {
        memset(vizitat,0,sizeof(vizitat));
        l_cuplaj += cuplare(i);
    }
}

void marcare_initiala()
{
    for (int i = 1; i <= n; ++i)
        marcat_a[cuplat[i]] = true; //0 nu conteaza
}

void marcare(int nod) //gestioneaza un nod din stanga nemarcat
{
    int dest;
    for (unsigned int i = 0; i < vecin[nod].size(); ++i)
    {
        dest = vecin[nod][i];
        if (!marcat_b[dest])
        {
            marcat_b[dest] = true;
            marcat_a[cuplat[dest]] = false;
            marcare(cuplat[dest]);
        }
    }
}

void minimum_vertex_cover()
{
    marcare_initiala();
    for  (int i = 1; i <= n; ++i)
        if (!marcat_a[i])
            marcare(i);
}

void scrie()
{
    printf("%d\n",2*n-l_cuplaj);
    for (int i = 1; i <= n; ++i)
    {
        if (marcat_a[i] && marcat_b[i])
            printf("0\n");
        if (!marcat_a[i] && marcat_b[i])
            printf("1\n");
        if (marcat_a[i] && !marcat_b[i])
            printf("2\n");
        if (!marcat_a[i] && !marcat_b[i])
            printf("3\n");
    }
}

int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    citeste();
    cuplaj();
    minimum_vertex_cover();
    scrie();
    return 0;
}