#include <cstdio>
#include <vector>
#include <bitset>
#define nmax 10005
using namespace std;
vector <int> v[nmax];
bitset <nmax> uz;
int n,m,st[nmax],dr[nmax];
int hop,sa[nmax],sb[nmax];

int cuplaj(int x)
{
    uz[x]=1;
    int i,y;
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (dr[y]==0) {
            st[x]=y;
            dr[y]=x;
            return 1;
        }
    }
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (!uz[dr[y]]&&cuplaj(dr[y])) {
            st[x]=y;
            dr[y]=x;
            return 1;
        }
    }
    return 0;
}
void suport(int x)
{
    int i,y;
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (!sb[y]) {
            sb[y]=1;
            sa[dr[y]]=0;
            suport(dr[y]);
        }
    }
}
int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    int i,j,a,b;
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++) {
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
    }
    bool ok;
    do {
        ok=false;
        uz.reset();
        for (i=1;i<=n;i++)
            if (!st[i]&&cuplaj(i))
                ok=true;
    } while (ok);

    for (i=1;i<=n;i++)
        if (st[i]) {
            hop++;
            sa[i]=1;
        }
    printf("%d\n",2*n-hop);

    for (i=1;i<=n;i++)
        if (!sa[i])
            suport(i);

    for (i=1;i<=n;i++)
        printf("%d\n",(1-sa[i])+(1-sb[i])*2);

    return 0;
}