#include <fstream>
#include <vector>

using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

const int nmax= 8191;

bool u[nmax*2+1], u2[nmax*2+1];
int p[nmax*2+1];
vector <int> v[nmax*2+1];

int pair_up( int x ) {
    if ( u[x]==1 ) {
        return 0;
    }
    u[x]= 1;

    for ( vector <int>::iterator it= v[x].begin(); it!=v[x].end(); ++it ) {
        if ( p[*it]==0 || pair_up(p[*it])==1 ) {
            u2[x]= 1;
            p[x]= *it, p[*it]= x;
            return 1;
        }
    }

    return 0;
}

void f( int x ) {
    for ( vector <int>::iterator it= v[x].begin(); it!=v[x].end(); ++it ) {
        if ( u2[*it]==0 ) {
            u2[*it]= 1, u2[p[*it]]= 0;
            f(p[*it]);
        }
    }
}

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1, x, y; i<=m; ++i ) {
        fin>>x>>y;
        v[x].push_back(n+y);
    }

    int cupmax= 0;
    for ( int ok= 1; ok>0; ) {
        ok= 0;
        for ( int i= 1; i<=n; ++i ) {
            u[i]= 0;
        }
        for ( int i= 1; i<=n; ++i ) {
            if ( p[i]==0 ) {
                ok+= pair_up(i);
            }
        }

        cupmax+= ok;
    }


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

    fout<<n*2-cupmax<<"\n";
    for ( int i= 1, aux= 0; i<=n; ++i, aux= 0 ) {
        if ( u2[i]==0 ) aux+= 1;
        if ( u2[n+i]==0 ) aux+= 2;
        fout<<aux<<"\n";
    }

    return 0;
}