#include <bits/stdc++.h>

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int nmax = 20005;
int N,M;
int st[nmax],dr[nmax];
vector < int > L[nmax];
bool viz[nmax],sifon[nmax];


inline void Read()
{
    int i,x,y;
    fin >> N >> M;
    for(i = 1; i <= M; i++)
    {
        fin >> x >> y;
        L[x].push_back(y + N);
    }
}


inline bool Cupleaza(int nod)
{
    int i;
    if(viz[nod]) return false;
    viz[nod] = true;
    for(auto it : L[nod])
    {
        if(!dr[it])
        {
            st[nod] = it;
            dr[it] = nod;
            return true;
        }
    }
    for(auto it : L[nod])
    {
        if(Cupleaza(dr[it]))
        {
            st[nod] = it;
            dr[it] = nod;
            return true;
        }
    }
    return false;
}



inline int Cuplaj()
{
    int i,j,ans,ok;
    ans = ok = 0;
    while(!ok)
    {
        ok = 1;
        for(i = 1; i <= N; i++) viz[i] = false;
        for(i = 1; i <= N; i++)
            if(!st[i] && Cupleaza(i))
        {
            ok = 0;
            ans++;
        }
    }
    return ans;
}

inline void Sifon_minim(int nod)
{
    for(auto it : L[nod])
    {
        if(!sifon[it])
        {
            sifon[it] = true;
            sifon[dr[it]] = false;
            Sifon_minim(dr[it]);
        }
    }
}


inline void Lavazza()
{
    int i;
    for(i = 1; i <= N; i++)
        if(st[i]) sifon[i] = true;
    for(i = 1; i <= N; i++)
        if(!st[i]) Sifon_minim(i);
}



inline void Solve()
{
    int i,OG;
    OG = Cuplaj();
    Lavazza();
    fout << 2*N - OG << "\n";
    for(i = 1; i <= N; i++)
    {
        if(sifon[i])
        {
            if(!sifon[i+N]) fout << "2\n";
            else fout << "0\n";
        }
        else
        {
            if(!sifon[i+N]) fout << "3\n";
            else fout << "1\n";
        }
    }
}

///PIEPT DE GORILA!
///FULL ADIDAS


int main()
{
    Read();
    Solve();
    fout.close();
    return 0;
}