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

using namespace std;

int N, M, uz[16384], st[16384], dr[16384], bst;
vector<int> G[8192];

int cupleaza(int nod)
{
    int i, x, sz;
    
    if (uz[nod])
        return 0;
        
    uz[nod] = 1;
    for (sz = G[nod].size(), i = 0; i < sz; i++)
    {
        x = G[nod][i];
        if (!dr[x] || cupleaza(dr[x]))
        {
            st[nod] = x;
            dr[x] = nod;
            return 1;
        }
    }

    return 0;
}

void check(int nod)
{
    int i, sz, x;

    for (sz = G[nod].size(), i = 0; i < sz; i++)
    {
        x = G[nod][i];
        if (!uz[x])
        {
            uz[dr[x]] = 0;
            uz[x] = 1;
            check(dr[x]);
        }
    }
    
}

int main(void)
{
    int i, j;
    
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for (; M; M--)
    {
        scanf("%d %d", &i, &j);
        G[i].push_back(N+j);
    }

    bst = 0;
    for (i = 1; i <= N; i++)
    {
        if (st[i]) continue;
        if (cupleaza(i)) bst++;
        else
        {
            memset(uz, 0, sizeof(uz));
            bst += (cupleaza(i));
        }
    }

    printf("%d\n", 2*N-bst);
    
    memset(uz, 0, sizeof(uz));
    for (i = 1; i <= N; i++)
        if (st[i])
            uz[i] = 1;
    for (i = 1; i <= N; i++)
        if (!st[i])
            check(i);

    for (i = 1; i <= 2*N; i++)
        uz[i] = !uz[i];

    for (i = 1; i <= N; i++)
        printf("%d\n", uz[i] + 2 * uz[i + N]);
            
    return 0;
}