#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

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

const int NMAX = 8192;

int n, m, cuplaj;

int l[NMAX], r[NMAX], d[NMAX];

bitset<NMAX> vizL, vizR;

vector<int> G[NMAX];
queue<int> q;

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

bool bfs() {
    while(!q.empty()) q.pop();

    bool ok = 0;
    for(int i = 1; i <= n; ++i) {
        if(!l[i]) {
            d[i] = 0;
            q.push(i);
        } else {
            d[i] = -1;
        }
    }

    while(!q.empty()) {
        int x = q.front();
        q.pop();

        for(int y : G[x]) {
            if(!r[y]) {
                ok = 1;
            } else if(d[r[y]] == -1) {
                d[r[y]] = d[x] + 1;
                q.push(r[y]);
            }
        }
    }

    return ok;
}

bool dfs(int x) {
    for(int y : G[x]) {
        if(!r[y] || (d[r[y]] == d[x] + 1 && dfs(r[y]))) {
            l[x] = y;
            r[y] = x;
            return 1;
        }
    }

    d[x] = -1;
    return 0;
}

void hopcroftKarp() {
    while(bfs()) {
        for(int i = 1; i <= n; ++i) {
            if(!l[i] && dfs(i)) {
                ++cuplaj;
            }
        }
    }
}

void dfsReconstructie(int x) {
    vizL[x] = 1;

    for(int y : G[x]) {
        if(l[x] == y || vizR[y]) continue;

        vizR[y] = 1;
        if(r[y] && !vizL[r[y]]) {
            dfsReconstructie(r[y]);
        }
    }
}

void reconstructie() {
    for(int i = 1; i <= n; ++i) {
        if(!l[i] && !vizL[i]) {
            dfsReconstructie(i);
        }
    }
}

void afis() {
    fout << 2 * n - cuplaj << '\n';
    for(int i = 1; i <= n; ++i) {
        fout << vizL[i] + 2 * (!vizR[i]) << '\n';
    }
}

int main() {
    citire();
    hopcroftKarp();
    reconstructie();
    afis();
    return 0;
}