#include <fstream>
#include <cstdio>
#include <vector>
#include <cstring>
#define Nmax 8191
using namespace std;

ofstream g("felinare.out");

vector<int> G[Nmax+1];

int i,n,x,y,l[Nmax+1],r[Nmax+1],nr,m;
bool ap[Nmax+1][2];
bool uz[Nmax+1];

bool cup(int nod)
{
    uz[nod] = 1;

    for (int i=0;i<G[nod].size();i++)
    {
        int crt = G[nod][i];
        if (!r[crt])
        {
            r[crt] = nod;
            l[nod] = crt;
            return 1;
        }
    }

    for (int i=0;i<G[nod].size();i++)
    {
        int crt = G[nod][i];
        if (!uz[r[crt]] && cup(r[crt]))
        {
            r[crt] = nod;
            l[nod] = crt;
            return 1;
        }
    }
    return 0;
}

void aprinde(int nod)
{
    for (int i=0;i<G[nod].size();i++)
    {
        int crt = G[nod][i];
        if (ap[crt][0])
        {
            ap[crt][0] = false;
            ap[r[crt]][1] = true;
            aprinde(r[crt]);
            return;
        }
    }
}


int main()
{
    freopen("felinare.in","r",stdin);

    scanf("%ld%ld",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%ld%ld",&x,&y);
        G[x].push_back(y);
    }

    bool change;

    do
    {
        change = false;
        memset(uz,0,sizeof(uz));

        for (int i=1;i<=n;i++)
        {
            if (!l[i])
            {
                int x = cup(i);
                change |= x;
                nr += x;
            }
        }
    }
    while (change);

    g<< 2 * n - nr<<'\n';

    for (int i=1;i<=n;i++)
            ap[i][0]=ap[i][1] = true;
    for (int i=1;i<=n;i++)
    {
        if (l[i])
            ap[i][1] = false;
    }

    for (int i=1;i<=n;i++)
        if (!l[i])
            aprinde(i);

    for (int i=1;i<=n;i++)
    {
        if (ap[i][0]==1 && ap[i][1] == 1)
            g<<3<<'\n';
        else if (ap[i][0]==1)
            g<<2<<'\n';
        else if (ap[i][1] == 1)
            g<<1<<'\n';
        else
            g<<0<<'\n';
    }

    return 0;
}