#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(R[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;

    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;
}