#include <bits/stdc++.h>

using namespace std;

const int NMAX = 8191;
int l[NMAX + 5],r[NMAX + 5],l1[NMAX + 5],r1[NMAX + 5];
vector <int> edge[NMAX + 5];
bool viz[NMAX + 5];

void init() {
    memset(viz, 0, sizeof(viz));
}
bool PairUp(int nod) {
    if (viz[nod])
        return 0;
    viz[nod] = 1;
    for (int i = 0;i < edge[nod].size();i++) {
        if (!l[edge[nod][i]]) {
            l[edge[nod][i]] = nod;
            r[nod] = edge[nod][i];
            l1[nod] = 1;
            return 1;
        }
    }
    for (int i = 0;i < edge[nod].size();i++) {
        if (PairUp(l[edge[nod][i]])) {
            r[nod] = edge[nod][i];
            l[edge[nod][i]] = nod;
            l1[nod] = 1;
            return 1;
        }
    }
    return 0;
}
void support(int nod) {
    for (int i = 0;i < edge[nod].size();i++) {
        if (!r1[edge[nod][i]]) {
            r1[edge[nod][i]] = 1;
            l1[l[edge[nod][i]]] = 0;
            support(l[edge[nod][i]]);
        }
    }
}
int main()
{
    ifstream fin("felinare.in");
    ofstream fout("felinare.out");
    int n,m,a,b,ok = 1,cnt = 0;
    fin >> n >> m;
    for (int i = 0;i < m;i++) {
        fin >> a >> b;
        edge[a].push_back(b);
    }
    while (ok) {
        ok = 0;
        init();
        for (int i = 1;i <= n;i++) {
            if (!r[i])
                ok |= PairUp(i);
        }
    }
    for (int i = 1;i <= n;i++)
        if (r[i])
            cnt++;
    for (int i = 1;i <= n;i++) {
        if (!l1[i])
            support(i);
    }
    fout << 2 * n - cnt << '\n';
    for (int i = 1;i <= n;i++)
        fout << 1 - l1[i] + 2 * (1 - r1[i]) << '\n';
    return 0;
}