#include <bits/stdc++.h>

using namespace std;

ifstream f ("felinare.in");
ofstream g ("felinare.out");

int n,m;
vector <int> v[10005];
int st[10005];
int dr[10005];
int viz[10005];
int cover[100005];
struct el
{
    int prim;
    int secund;
};
el query[100005];

int pairup(int nod)
{
    if(viz[nod]==1)
        return 0;
    viz[nod]=1;
    if(st[nod]==0)
    {
        for(int x=0; x<v[nod].size(); ++x)
        {
            int fiu=v[nod][x];
            if(dr[fiu]==0)
            {
                st[nod]=fiu;
                dr[fiu]=nod;
                return 1;
            }
        }
    }
    for(int x=0; x<v[nod].size(); ++x)
    {
        int fiu=v[nod][x];
        if(pairup(dr[fiu]))
        {
            st[nod]=fiu;
            dr[fiu]=nod;
            return 1;
        }
    }
    return 0;

}
int supst[10005];
int supdr[10005];

void suport(int nod)
{
    for(int i=0; i<v[nod].size(); i++)
    {
        if(!supdr[v[nod][i]])
        {
            supdr[v[nod][i]]=1;
            supst[dr[v[nod][i]]]=0;
            suport(dr[v[nod][i]]);
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y;
        f>>x>>y;
        query[i].prim=x;
        query[i].secund=y;
        v[x].push_back(y);

    }
    int ok=0;
    while(ok==0)
    {
        ok=1;
        for(int i=1; i<=n; ++i)
            viz[i]=0;
        for(int i=1; i<=n; ++i)
        {
            if(st[i]==0 && pairup(i))
                ok=0;
        }
    }
    int cont=0;

    for(int i=1; i<=n; ++i)
    {
        if(st[i]!=0)
        {
            supst[i]=1;
            ++cont;
        }
    }
    g<<2*n-cont<<"\n";



    for(int i=1; i<=n; ++i)
    {
        if(supst[i]==0)
            suport(i);
    }
    for(int i=1; i<=n; ++i)
    {

        if(supst[i]==0 && supdr[i]==0)
            g<<3<<"\n";

        if(supst[i]==1 && supdr[i]==0)
            g<<2<<"\n";

        if(supst[i]==0 && supdr[i]==1)
            g<<1<<"\n";

        if(supst[i]==1 && supdr[i]==1)
            g<<0<<"\n";
    }
    return 0;
}