#include <bits/stdc++.h>

using namespace std;

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

const int nmax=1e4+5;

int n,m,e;
int st[nmax],dr[nmax],out[nmax];

bool used[nmax];
bool change;

vector <int> gr[nmax];

bool cupleaza(int nod)
{
    if ( used[nod] ) return false;

    used[nod]=true;

    for (auto x:gr[nod] )
    {
        if ( !dr[x] )
        {
            st[nod]=x;
            dr[x]=nod;

            return true;
        }
    }

    for (auto x:gr[nod] )
    {
        if ( cupleaza(dr[x]) )
        {
            st[nod]=x;
            dr[x]=nod;
            return true;
        }
    }

    return false;
}

void reset()
{
    change=false;
    for (int i=1; i<=n; i++ )
        used[i]=false;
}

void mvc(int nod)
{
    if ( used[nod] ) return;

    used[nod]=1; // marcam out(nod) ca vizitat

    for (auto x:gr[nod] ) // pt fiecare x(in) care are muchie cu nod(out)
        if ( st[nod]!=x && !out[x] ) {
             out[x]=1;
             mvc(dr[x]);
    }
}

int main()
{
    f >> n >> m;

    for (int i=1; i<=m; i++ )
    {
        int x,y; f >> x >> y;
        gr[x].push_back(y);
    }

    // nr de felinare aprinse= 2n-m, pt ca noi tb sa sarim
    // cate un nod din fiecare muchie m, pt a nu ilumina intreaga strada

    change=true;
    while ( change==true )
    {
        reset();

        for (int i=1; i<=n; i++ )
            if ( !st[i] && cupleaza(i) )
                change=true;
    }

    int nr=0;
    for (int i=1; i<=n; i++ )
        if ( st[i]>0 )
            nr++;

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

    reset();
    for (int i=1; i<=n; i++ )
        if ( st[i]==0 )
            mvc(i);

    for (int i=1; i<=n; i++ )
        g << used[i]+2*(1-out[i]) << '\n';
    return 0;
}