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

using namespace std;

#define MAX_N 1<<14
#define FIN "felinare.in"
#define FOUT "felinare.out"
#define left(x) ((x)<<1)
#define right(x) (((x)<<1)|1)
#define pb push_back

int N, M, Res, P[MAX_N]; char U[MAX_N];
vector<int> G[MAX_N];

int match(int n)
{
    vector<int>::iterator it;

    if (U[n]) return 0;
    U[n] = 1;
    for (it = G[n].begin(); it != G[n].end(); it++)
        if (P[*it] == -1 || match(P[*it]))
        {
            P[n] = *it; P[*it] = n;
            return 1;
        }
    return 0;
}

void cover(int n)
{
    vector<int>::iterator it;

    for (it = G[n].begin(); it != G[n].end(); it++)
    {
        if (U[*it]) continue;
        U[P[*it]] = 0; U[*it] = 1;
        cover(P[*it]);
    }
}

int main(void)
{
    int i, j, ok;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

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

    memset(P, -1, sizeof(P));
    for (ok = 1; ok; )
    {
        memset(U, 0, sizeof(U));
        for (ok = i = 0; i < N; i++)
            if (P[left(i)] == -1 && match(left(i))) { Res++; ok = 1; }
    }

    printf("%d\n", 2*N-Res);
    memset(U, 0, sizeof(U));
    for (i = 0; i < N; i++) 
        if (P[left(i)] != -1) U[left(i)] = 1;
    for (i = 0; i < N; i++)
        if (!U[left(i)]) cover(left(i));
    for (i = 0; i < N; i++)
        printf("%d\n", (!U[right(i)]<<1)|!U[left(i)]);

    return 0;
}