#include <bits/stdc++.h>

using namespace std;

const int NMAX = 8192;

ifstream f("felinare.in");
ofstream g("felinare.out");

vector<int> G[NMAX];
int N, M, maxMatch,
    L[NMAX], R[NMAX];
bool viz[NMAX], sL[NMAX], sR[NMAX];

void citire()
{
    int x, y;
    f >> N >> M;
    while(M--)
    {
        f >> x >> y;
        G[x].push_back(y);
    }
}

bool DFS(int x)
{
    if(viz[x])return 0; ///daca a mai fost folosit in iteratia curenta, ne intoarcem
    viz[x] = 1;
    for(auto &y : G[x])
        if(L[y] == 0 || DFS(L[y])) ///incercam sa-l cuplam cu un nod adiacent
        {
            L[y] = x;
            R[x] = y;
            sL[x] = 1; //(*)
            return 1;
        }
    return 0;
}

void HK()
{
    bool wasChanged = 1;
    int i;
    while(wasChanged) ///cat timp s-a facut o cuplare in iteratia anterioara => este posibil sa mai putem cupla
    {
        wasChanged = 0;
        for(i = 1; i <= N; ++i)
            viz[i] = 0;
        for(i = 1; i <= N; ++i)
            if(!R[i] && DFS(i))
                wasChanged = 1, ++maxMatch;
    }
}

void suport(int x)
{
    for(auto &y : G[x])
        if(!sR[y])
        {
            sR[y] = 1;
            sL[L[y]] = 0;
            suport(L[y]);
        }
}

int main()
{
    int t;
    citire();
    HK();
//    for(int i = 1; i <= N; ++i)  (*)
//        if(R[i])sL[i] = 1;

    for(int i = 1; i <= N; i++)
        if(!sL[i])
            suport(i);

    g << 2 * N - maxMatch << '\n';

    for(int i = 1; i <= N; ++i)
    {
        if(sL[i] && sR[i])
            t = 0;
        else if(sR[i])
            t = 1;
        else if(sL[i])
            t = 2;
        else t = 3;
        g << t << '\n'; ///t=3-sL[i]-2*sR[i];
    }
    return 0;
}


/**
 Felinar ==> http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=597
*/

/**
  Pornind de la graful iniţial, construim un nou graf bipartit, după cum urmează:

  ● în stânga N noduri corespunzătoare felinarelor de tipul 1,
  ● în dreapta N noduri corespunzătoare felinarelor de tipul 2.

  O muchie i -> j din graful iniţial va deveni o muchie între nodul i din stânga
  şi nodul j din dreapta în noul graf bipartit.

  Se observă că o stradă i -> j este complet iluminată dacă şi numai dacă atât felinarul
  corespunzător nodului i din stânga cât şi felinarul corespunzător nodului j din dreapta
  sunt aprinse.

  În concluzie, având dat un graf bipartit va trebui să alegem un număr maxim de noduri
  astfel încât să nu existe nicio muchie cu ambele extremități selectate.

  Adică trebuie să determinăm o "mulţime independentă maximală".

  Definiții și rezultate teoretice: (https://www.infoarena.ro/flux-si-cuplaj)
  =================================

  Suport minim = Într-un graf bipartit un suport minim reprezintă o mulţime de noduri S (inclusă în V)
  ------------   cu cardinal minim, pentru care orice muchie a grafului este incidentă cu cel puţin
                 unul dintre nodurile mulţimii.

  Mulţime independentă maximală = Într-un graf bipartit o mulţime independentă maximală reprezintă
  -----------------------------   o mulţime de noduri astfel încât oricare 2 noduri din mulţime
                                  să nu fie legate printr-o muchie, iar orice muchie din graf să aiba
                                  unul din noduri în mulţimea independentă.
  Observații:
  ==========
  1) Mulţimea independentă maximală este complementara unui suport minim în sensul că,
     daca avem un suport minim, o mulţime independentă maximală va fi formată din nodurile
     care nu aparţin suportului minim.

  2) Teoremă (König)
     ==============
     Într-un graf bipartit cuplajul maxim M şi suportul minim S au același cardinal,
     adică | M | = | S |.

     Un suport minim S se poate determina pornind de la orice cuplaj maxim M.

     Nodurile din prima mulţime L care aparţin cuplajului vor fi incluse în suportul minim,
     iar pentru cele care nu aparţin cuplajului vom folosi o funcţie recursiva care,
     în momentul în care gaseşte o muchie care nu are cel puţin un nod în suport,
     adauga nodul din R şi şterge nodul din stânga cu care este cuplat nodul respectiv,
     apoi apelează recursiv pentru nodul din stânga.

    Funcţia recursiva arata astfel:

   void suport(int x)
   {
   for(auto &y : G[x])    //pentru fiecare nod y (din dreapta) adiacent cu x
    {
        if(!sR[y])        //daca nu e in suport
        {
            sR[y] = 1;    //il adaug in suport
            sL[L[y]] = 0; //sterg din suport nodul din stanga cu care este cuplat y
            suport(L[y]); //apelez recursiv pentru nodul din stanga
        }
    }
  }
*/