#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#define pb push_back
#define nmax 17500

using namespace std;

vector <int> a[nmax];
bool used[nmax], usedright[nmax], usedleft[nmax];
int l[nmax], r[nmax];
int i, j, m, n, change, x, y, cuplaj;

inline int mp(int x)
{
    if(used[x]) return 0;
    used[x]=true;
    vector<int>::iterator it;

    for(it=a[x].begin(); it!=a[x].end(); ++it)
    if(!r[*it])
    {
        r[*it]=x;
        l[x]=*it;
        usedright[x]=true;
        return 1;
    }

    for(it=a[x].begin(); it!=a[x].end(); ++it)
    if(mp(r[*it]))
    {
        r[*it]=x;
        l[x]=*it;
        usedright[x]=true;
        return 1;
    }
    return 0;
}

void change_type(int node)
{
    vector<int>::iterator it;

    for(it=a[node].begin(); it!=a[node].end(); ++it)
    if (!usedleft[*it])
    {
        usedleft[*it]=true;
        usedright[r[*it]]=false;
        change_type(r[*it]);
    }
}

int main()
{
    freopen("felinare.in", "rt", stdin);
    freopen("felinare.out", "wt", stdout);

    scanf("%d%d", &n, &m);

    for(i=1; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        a[x].pb(y);
    }

    for(change=1; change; )
    {
        change=0;
        memset(used, false, sizeof(used));
        for(i=1; i<=n; ++i)
            if(!l[i]) change|=mp(i);
    }

    for(i=1; i<=n; ++i)
        if(l[i]) ++cuplaj;

    printf("%d\n", 2*n-cuplaj);

    for(i=1; i<=n; ++i)
        if(!usedright[i]) change_type(i);

    for(i=1; i<=n; ++i)
        printf("%d\n", 2*(usedleft[i]^1)+(usedright[i]^1));

    return 0;
}