#include <bits/stdc++.h>

const int MAX_N = 8191;

using namespace std;

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

int n, m;
int l[MAX_N + 5], r[MAX_N + 5];
int openl[MAX_N + 5], openr[MAX_N + 5];
bool visited[MAX_N + 5];

vector<int> G[MAX_N + 5];

bool cuplaj(int u) {
    if (visited[u])
        return 0;

    visited[u] = 1;

    for (int v : G[u])
        if (r[v] == 0) {
            l[u] = v;
            r[v] = u;
            return 1;
        }

    for (int v : G[u])
        if (cuplaj(r[v])) {
            l[u] = v;
            r[v] = u;
            return 1;
        }

    return 0;
}

void dfs(int u) {
    for (int v : G[u])
        if (!openr[v]) {
            openr[v] = 1;
            dfs(r[v]);
        }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        fin >> u >> v;
        G[u].push_back(v);
    }

    bool ok;
    int ans = 0;
    do {
        ok = 0;
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++)
            if (l[i] == 0 && cuplaj(i)) {
                ok = 1;
                ans++;
            }
    } while(ok);

    fout << 2 * n - ans << '\n';

    for (int i = 1; i <= n; i++)
        if (l[i] == 0)
            dfs(i);

    for (int i = 1; i <= n; i++)
        if (l[i] && !openr[l[i]])
            openl[i] = 1;

    for (int i = 1; i <= n; i++) {
        if (openl[i] && openr[i])
            fout << 0 << '\n';
        else if(!openl[i] && openr[i])
            fout << 1 << '\n';
        else if(openl[i] && !openr[i])
            fout << 2 << '\n';
        else
            fout << 3 << '\n';
    }

    return 0;
}