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

using namespace std;

#define Nmax 9000
vector<int> l[Nmax];
int N,M,s[Nmax],sr[Nmax];
int p[Nmax],r[Nmax],v[Nmax];

void suport(int k)
{
    vector<int>::iterator it;

    for(it=l[k].begin();it!=l[k].end();++it)
        if (!sr[ *it ])
            {
            sr[ *it ]=1;
            s[ r[*it] ]=0;
            suport(r[*it]);
            }
}

int pairup(int k)
{
    if (v[k])
        return 0;
    v[k]=1;

    vector<int>::iterator it;
    for(it=l[k].begin();it!=l[k].end();++it)
        if (!r[ *it ])
            {
            p[k] = *it;
            r[ *it ]=k;
            return 1;
            }
    for(it=l[k].begin();it!=l[k].end();++it)
        if (k!=r[ *it ] && pairup(r[*it]))
            {
            p[k] = *it;
            r[ *it ]=k;
            return 1;
            }
    return 0;
}

void solve()
{
    int cuplaj=0;
    for(int ok=1;ok;)
        {
        ok=0;
        memset(v,0,sizeof(v));
        for(int i=1;i<=N;++i)
            if (!p[i] && pairup(i))
                {
                ok = 1;
                cuplaj++;
                }
        }
    printf("%d\n",2*N-cuplaj);
    for(int i=1;i<=N;++i)
        if (p[i])
            s[i]=1;
    for(int i=1;i<=N;++i)
        if (!p[i])
            suport(i);

    for(int i=1;i<=N;++i)
        printf("%d\n",(sr[i]^1)*2 + (s[i]^1));
}

void cit();

int main()
{
    cit();
    solve();
    return 0;
}

void cit()
{
    int a,b;
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
        {
        scanf("%d%d",&a,&b);
        l[a].push_back(b);
        }
}