#include <bits/stdc++.h>

using namespace std;

const int Nmax = (1 << 13);

int n , m , i;
int L[Nmax] , R[Nmax] , S[Nmax << 1];

bool marked[Nmax];

vector < int > g[Nmax];

#define R (R - (n))

bool pairUp(int node)
{
    marked[node] = 1;

    for (auto &it : g[node])
        if (!R[it])
        {
            L[node] = it; R[it] = node;
            return 1;
        }

    for (auto &it : g[node])
        if (!marked[R[it]] && pairUp(R[it]))
        {
            L[node] = it; R[it] = node;
            return 1;
        }

    return 0;
}

void support(int node)
{
    for (auto &it : g[node])
        if (!S[it])
        {
            S[it] = 1; S[R[it]] = 0;
            support(R[it]);
        }
}

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

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

    for (i = 1; i <= m; ++i)
    {
        int node1 , node2;
        scanf("%d %d", &node1, &node2);
        g[node1].push_back(node2+n);
    }

    for (bool ok = 1; ok ; )
    {
        for (i = 1; i <= n; ++i) marked[i] = 0; ok = 0;

        for (i = 1; i <= n; ++i)
            if (!L[i]) ok |= pairUp(i);
    }

    int s = 0;
    for (i = 1; i <= n; ++i)
        s += S[i] = (L[i] != 0);

    for (i = 1; i <= n; ++i)
        if (!L[i]) support(i);

    printf("%d\n", (n << 1) - s);
    for (i = 1 ; i <= n; ++i)
        printf("%d\n", ((!S[i+n]) << 1) + (!S[i]));

    return 0;
}