#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 8195;

vector<int> g[2 * NMAX];
int n, m, dist[2 * NMAX], match[2 * NMAX];

bool dfs(int u) {
    for(auto v : g[u]) {
        int u2 = match[v];
        if(u2 == 0) {
            match[v] = u;
            match[u] = v;
            return 1;
        }
        if(dist[u2] == dist[u] + 1) {
            bool state = dfs(u2);
            if(state == 1) {
                match[v] = u;
                match[u] = v;
                return 1;
            }
        }
    }
    return 0;
}

void bfs() {
    queue<int> q;
    for(int i = 1; i <= n; i ++) {
        if(match[i] == 0) {
            dist[i] = 0; /// atentie aici
            q.push(i);
        } else
            dist[i] = -1;
    }

    while(q.size()) {
        int u = q.front();
        q.pop();
        for(auto v : g[u]) {
            int u2 = match[v];
            if(u2 && dist[u2] == -1) {
                dist[u2] = dist[u] + 1;
                q.push(u2);
            }
        }
    }
}

int hopcroftkarp() {
    bool found = 1;
    int ans = 0;
    while(found) {
        found = 0;
        bfs();
        for(int i = 1; i <= n; i ++)
            if(dist[i] == 0 && dfs(i) == 1) {
                found = 1;
                ans ++;
            }
    }
    return ans;
}

int ison[NMAX * 2];

void turnoff(int u) {
    ison[u] = 0;
    for(auto v : g[u]) {
        if(!ison[v]) {
            ison[v] = 1;
            int u2 = match[v];
            if(ison[u2])
                turnoff(u2);
        }
    }
}

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

    int ans = n * 2 - hopcroftkarp();
    out << ans << "\n";
    for(int i = 1; i <= n; i ++)
        ison[i] = 1;
    for(int i = 1; i <= n; i ++)
        if(!match[i] && ison[i] == 1)
            turnoff(i);

    for(int i = 1; i <= n; i ++)
        out << (1 * (ison[i] ^ 1) + 2 * (ison[i + n] ^ 1)) << "\n";
    return 0;
}