#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

#define maxn 8192
#define pb push_back

long n, i, j, k, m, a, b, sol, cuplaj[maxn], viz[maxn], inv[maxn], ap[maxn][2];
vector <long> v[maxn];

long cupleaza(long nod)
{
    long i, fiu;
    if(viz[nod]) return 0;
    viz[nod]=1;
    for(i=0; i<v[nod].size(); i++)
    {
        fiu=v[nod][i];
        if(!cuplaj[fiu])
        {
            cuplaj[fiu]=nod;
            return 1;
        }
    }
    for(i=0; i<v[nod].size(); i++)
    {
        fiu=v[nod][i];
        if(cuplaj[fiu]!=nod)
        if(cupleaza(cuplaj[fiu]))
        {
            cuplaj[fiu]=nod;
            return 1;
        }
    }
    return 0;
}     

void df(long nod)
{
    long i, vec;
    if(viz[nod]) return;
    viz[nod]=1;
    for(i=0; i<v[nod].size(); i++)
    {
        vec=v[nod][i];   
        if(ap[vec][1]==1)
        {
            ap[vec][1]=0;
            if(cuplaj[vec])
            {
                ap[cuplaj[vec]][0]=1;
                df(cuplaj[vec]);
            }
        }
    }
}            

int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &a, &b);
        v[a].pb(b);
    }
    sol=0;
    for(i=1; i<=n; i++)
    {
        ap[i][1]=1; ap[i][0]=1;
        memset(viz, 0, sizeof(viz));
        sol+=cupleaza(i);
    }
    printf("%d\n", 2*n-sol);
    for(i=1; i<=n; i++)
    {
        if(cuplaj[i])
        {
            inv[cuplaj[i]]=i;
            ap[cuplaj[i]][0]=0;
        }
    }
    memset(viz, 0, sizeof(viz));
    for(i=1; i<=n; i++)
    {
        if(inv[i]==0) df(i);
    }
    for(i=1; i<=n; i++)
    {
        printf("%d\n", ap[i][1]*2+ap[i][0]);
    }
    return 0;
}