#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin ("felinare.in"); ofstream fout ("felinare.out");

const int nmax = 8191;

int l[nmax + 1], r[nmax + 1];
bool viz[2 * nmax + 1];

vector< int > g[nmax + 1];

bool pair_up (int nod) {
    if (viz[ nod ] == 1) return 0;
    viz[ nod ] = 1;

    for (auto i : g[ nod ]) {
        if (l[ i ] == 0) {
            l[ i ] = nod;
            r[ nod ] = i;
            return 1;
        }
    }

    for (auto i : g[ nod ]) {
        if (pair_up(l[ i ])) {
            l[ i ] = nod;
            r[ nod ] = i;
            return 1;
        }
    }
    return 0;
}

void reconst (int nod) {
    viz[ nod ] = 1;

    for (auto i : g[ nod ]) {
        viz[i + nmax] = 1;

        if (viz[ l[ i ] ] == 0) {
            reconst(l[ i ]);
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        g[ x ].push_back( y );
    }

    int ans = 0;
    bool ok = 1;
    while ( ok ) {
        memset(viz, 0, sizeof(viz));
        ok = 0;

        for (int i = 1; i <= n; ++ i) {
            if (r[ i ] == 0 && pair_up( i )) {
                ok = 1;
                ++ ans;
            }
        }
    }

    memset(viz, 0, sizeof(viz));
    for (int i = 1; i <= n; ++ i) {
        if (r[ i ] == 0) {
            reconst( i );
        }
    }

    fout << 2 * n - ans << "\n";
    for (int i = 1; i <= n; ++ i) {
        fout << viz[ i ] + 2 * (!viz[i + nmax]) << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}