#include <bits/stdc++.h>
#define NM 2*8195
using namespace std;
ifstream fin ("felinare.in");
ofstream fout ("felinare.out");
void read();
vector<int> v[NM];
int n, m, ma[NM], cp;
bitset<NM> viz, st, in;
int cuplaj(int nod)
{
    if(viz[nod])
        return 0;
    viz[nod] = 1;
    for(auto it:v[nod])
        if(!viz[it] && !ma[nod])
        {
            ma[it] = nod;
            ma[nod] = it;
            return 1;
        }
    for(auto it:v[nod])
        if(!viz[it] && ma[nod] && cuplaj(ma[nod]))
        {
            ma[it] = nod;
            ma[nod] = it;
            return 1;
        }
    return 0;
}
void dfs(int nod)
{
    if(viz[nod])
        return ;
    viz[nod] = 1;
    for(auto it:v[nod])
        if(!viz[it] && !ma[it])
        {
            viz[it] = 1;
            return ;
        }
        else if(!viz[it] && ma[it])
        {
            viz[it] = 1;
            dfs(ma[it]);
        }
}
int main()
{
    read();
    bool ok = 1;
    while(ok)
    {
        for(int i=1; i<=2*n; ++i)
            viz[i] = 0;
        ok = 0;
        for(int i=1; i<=n; i++)
            if(!viz[i] && !ma[i])
            {
                if(cuplaj(i))
                    ok = 1;
            }
    }
    for(int i=1; i<=n; i++)
        if(ma[i])
            cp++;
    for(int i=1; i<=2*n; i++)
        viz[i] = 0;
    for(int i=1; i<=n; i++)
        if(!ma[i])
            dfs(i);
    for(int i=n+1; i<=2*n; i++)
        if(viz[i])
            st[i] = 1;
    for(int i=1; i<=n; i++)
        if(!viz[i])
            st[i] = 1;
    int nr = 0;
    for(int i=1; i<=2*n; i++)
        if(!st[i])
            ++nr, in[i] = 1;
    fout << 2*n-cp << '\n';
    for(int i=1; i<=n; i++)
        if(!in[i] && !in[i+n])
            fout << 0 << '\n';
        else if(in[i] && !in[i+n])
            fout << 1 << '\n';
        else if(!in[i] && in[i+n])
            fout << 2 << '\n';
        else fout << 3 << '\n';
    return 0;
}
void read()
{
    fin >> n >> m;
    for(int i=1; i<=m; ++i)
    {
        int x, y;
        fin >> x >> y;
        y+=n;
        v[x].push_back(y);
    }
}