#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define nmax 8192

int n, m, st[nmax], dr[nmax], inSuportSt[nmax], inSuportDr[nmax];
bool viz[nmax];
vector<int> gf[nmax];

void citeste(){
    f >> n >> m;
    int x, y;
    for(int i=1; i<=m; ++i){
        f >> x >> y;
        gf[x].push_back(y);
    }
}

inline int cupleaza(int nod){
    if (viz[nod] == 1) return 1;
    viz[nod] = 1;
    // incerc sa il cuplez pe nod cu ceva vecin de al lui
    for(int i=0; i<gf[nod].size(); ++i){
        int vc = gf[nod][i];
        if (dr[vc] == 0){
            st[nod] = vc; dr[vc] = nod;
            return 1;
        }
    }

    // acum incerc ce cuplez pe nod cu un vecin recupland nodul cu care era cuplat vecin cu un alt nod
    for(int i=0; i<gf[nod].size(); ++i){
        int vc = gf[nod][i];
        if (cupleaza( dr[vc] ) > 0){// daca am reusit sa il recuplez pe nodul din stanga cu care era
        // cuplat vc
        st[nod] = vc; dr[vc] = nod;
        return 1;
        }
    }
    return 0;
}

inline int bagaCuplaj(){
    int Card = 0;
    for(int ok=1; ok!=0;){
        ok = 0;
        for(int i=1; i<=n; ++i) viz[i] = 0;
        for(int i=1; i<=n; ++i){
            if (st[i] == 0 && cupleaza(i) > 0){// daca nodul i nu e cuplat si daca il pot cupla
                ok = 1; ++Card;
            }
        }
    }
    return Card;
}

void bagaInSuport(int nod){
    for(int i=0; i<gf[nod].size(); ++i){
        int vc = gf[nod][i];
        if (inSuportDr[vc] == 0){// daca nu e in suport
            inSuportDr[ vc ] = 1;
            inSuportSt[ dr[vc] ] = 0;// scot nodul cu care era cuplat nodul vc din a 2 multime
            bagaInSuport( dr[vc] );
        }
    }
}

void suportMin(){
    // orice nod din partea stanga care se afla in cuplaj va face parte si din suport
    for(int i=1; i<=n; ++i){
        if (st[i] != 0){// daca nodul din i din multimea din partea stanga se afla in cuplaj
            inSuportSt[i] = 1;// nodul din i din partea stanga se afla in suport
        }
    }

    // acum incerc sa bag in suport noduri din partea stanga care nu erau in cuplaj
    for(int i=1; i<=n; ++i){
        if (st[i] == 0){
            bagaInSuport(i);
        }
    }
}

void rezolva(){
    // numarul maxim de felinare pe care le pot aprinde ar fi n * 2;
    // eu stiu ca pe orice muchie nu vreau sa fie ambele felinare aprinse; => vreau sa sting
    // un numar minim de noduri a. i. fiecare muchie sa aiba cel putin un felinar stins
    // bag un cuplaj; si dupa sting felinarele nodurilor din stanga => n*2-card_cuplaj;
    // apoi am nevoie sa determin o multime de noduri a. i. fiecare muchie sa aiba unul
    // dintre capete in multime; multimea asta se numeste suport minim; numarul lor e egal cu
    // cuplajul maxim doar ca trebuie sa le si determin; avand un suport minim fixat
    // eu pot afla raspunsul cerut adica o multime de noduri a. i. oricare 2 noduri din multime
    // sa nu aiba vreo muchie intre ei si oricare muchie din graf sa aiba un capat in multime
    // asta se numeste  multime independenta maximala care e defapt complementul suportului minim
    g << n*2-bagaCuplaj() << "\n";
    // acum bag suportul minim pornind de la cuplajul maxim obtinut
    // acum stiind suportul aflu multimea independenta maximala
    //adica daca se afla in suport => nu o sa se afle in multime independenta maximala
    suportMin();

    for(int i=1; i<=n; ++i){
        //cout << inSuportSt[i] << " " << inSuportDr[i] << "\n";
        if (inSuportSt[i] == 1 && inSuportDr[i] == 1){// ambele noduri se afla in suport
        // => nu se afla in multime => le sting felinarele
            g << 0 << "\n";
        }else if (inSuportSt[i] == 1 && inSuportDr[i] == 0){// ala din stanga il sting ala din dreapta il aprind
            g << 2 << "\n";
        }else if (inSuportSt[i] == 0 && inSuportDr[i] == 1){
            g << 1 << "\n";
        }else {// le aprind pe amandoua pt ca nu se afla in suport;
            g << 3 << "\n";
        }
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}