#include <bits/stdc++.h>

using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
const int N=20000;
vector<int> v[N];
int viz[N];
int n,m,st[N],dr[N],stins[N],cupleaza(int),APRINSE,start;
void stinge(int);
int main()
{
    f>>n>>m;
    for(; m; m--)
    {
        int x,y;
        f>>x>>y;
        v[x].push_back(n+y);
        v[n+y].push_back(x);
    }
    /// Faza 1: Cuplaj maxim in graf bipartit MVC=CUPLAJ si APTINSE=2*n-MVC
    APRINSE=2*n;
    for(int i=1; i<=n; i++)
        APRINSE-=cupleaza(start=i);
    g<<APRINSE<<'\n';
    /// Faza 2: MODIFIC CUPLAJ in MCV
    for(int i=1; i<=n; i++)
        if(dr[i])stins[i]=1;
    for(int i=1; i<=n; i++)
        if(!dr[i])stinge(i);
    for(int i=1;i<=n;i++)
        g<<3-stins[i]-2*stins[n+i]<<'\n';
    return 0;
}
int cupleaza(int nod)
{
    if(viz[nod]==start)return 0;
    viz[nod]=start;
    for(auto vec:v[nod])
        if(st[vec]==0 || cupleaza(st[vec]))
        {
            dr[nod]=vec;
            st[vec]=nod;
            return 1;
        }
    return 0;
}
void stinge(int nod)
{
    for(auto vec:v[nod])
        if(!stins[vec])
        {
            stins[vec]=1;
            stins[st[vec]]=0;
            stinge(st[vec]);
        }
}
/// Problema se traduce astfel:
/// pentru fiecare nod x din graful initial orientat se creaza doua varfuri intr-un graf bipartit (neorientat)
/// varful x - corespunde becului 1 din k
/// verful x+n - corespunde becului 2 din k
/// in fiecare nod 1...2n avem un bec
/// in acest fel se creaza un graf bipartit in care fiecare arc (x,y) din graful initial
/// devine muchia [x,n+y] in graful bipartit
/// Pe arcul (x,y) vrem sa avem stins fie becul 1 din x fie becul 2 din y
/// Traducem asta prin : pentru fiecare muchie [x,n+x] vrem sa avem  stins becul din x sau becul din y+n
/// Fie multimea S a becurilor stinse. Atunci multimea S trebuie sa indeplineasca conditia ca pentru
/// orice muchie a grafului bipartit sa am macar unul dintre cele doua capete in S
/// In plus vrem ca multimea S sa contina un numar minim de varfuri
/// CONCLUZIE : In graful bipartit dorim multimea S de cardinal minim astfel incat fiecare muchie sa fie
/// incidenta macar unui varf din S
/// In orice graf neorientat o astfel de multime se numeste "minimum vertex cover" (MVC)
/// problema de rezolvat "MINIMUM VERTEX COVER IN BIPARTITE GRAPH" ( google it !!! )