#include<fstream>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
#define NMAX 8195
ifstream fin("felinare.in");
ofstream fout("felinare.out");
vector <int> v[NMAX];
vector < pair <int,int> > V;
bitset <NMAX> viz;
int n,m,x,y,nr,D[2][NMAX],L[NMAX],R[NMAX],N[NMAX];
bool cupleaza(int nod)
{
    int i;
    if (viz[nod]) return false;
    viz[nod]=1;
    for (i=0;i<v[nod].size();++i)
        if (!R[v[nod][i]])
        {
            L[nod]=v[nod][i];
            R[v[nod][i]]=nod;
            return true;
        }
    for (i=0;i<v[nod].size();++i)
        if (cupleaza(R[v[nod][i]]))
        {
            L[nod]=v[nod][i];
            R[v[nod][i]]=nod;
            return true;
        }
    return false;
}
bool cmp(pair <int,int> A, pair <int,int> B)
{
    return D[A.second][A.first]>D[B.second][B.first];
}
int main()
{
    int i;
    bool ok;
    fin>>n>>m;
    for (i=1;i<=m;++i)
    {
        fin>>x>>y;
        ++D[0][x], ++D[1][y];
        v[x].push_back(y);
    }
    for (ok=true;ok;)
    {
        ok=false;
        viz.reset();
        for (i=1;i<=n;++i)
            if (!L[i] && cupleaza(i))
                ok=true;
    }
    for (i=1;i<=n;++i)
    {
        if (L[i])
        {
            ++nr;
            V.push_back(make_pair(i,0));
            V.push_back(make_pair(L[i],1));
        }
        N[i]=3;
    }
    sort(V.begin(),V.end(),cmp);
    for (i=0;i<nr;++i)
        if (V[i].second)
            N[V[i].first]-=2;
        else
            --N[V[i].first];
    fout<<2*n-nr<<"\n";
    for (i=1;i<=n;++i)
        fout<<N[i]<<"\n";
    return 0;
}