#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

#define ITERATOR vector<int>::iterator
const int NMAX = 8200;

int left[NMAX], right[NMAX], leftMVC[NMAX], rightMVC[NMAX], vis[NMAX];
vector <int> graph[NMAX];

int pairUp (int node) {
    if(vis[node])
        return 0;

    vis[node] = 1;
    for(ITERATOR it = graph[node].begin(); it != graph[node].end(); ++ it)
        if(!left[*it] || pairUp(left[*it])) {
            left[*it] = node;
            right[node] = *it;

            return 1;
        }
     return 0;
}

void f (int node) {
    for(ITERATOR it = graph[node].begin(); it != graph[node].end(); ++ it)
        if(!leftMVC[*it]) {
            leftMVC[*it] = 1;
            rightMVC[left[*it]] = 0;

            f(left[*it]);
        }
}

int main() {
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    int x, y, i, nPairs, n, m;

    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++ i) {
        scanf("%d%d", &x, &y);
        graph[x].push_back(y);
    }

    nPairs = 0;
    for(i = 1; i <= n; ++ i) {
        memset(vis, 0, sizeof(vis));
        nPairs += pairUp(i);
    }

    for(i = 1; i <= n; ++ i)
        if(right[i])
            rightMVC[i] = 1;

    for(i = 1; i <= n; ++ i)
        if(!rightMVC[i])
            f(i);

    printf("%d\n", 2 * n - nPairs);
    for(i = 1; i <= n; ++ i) {
        if(leftMVC[i] == 0 && rightMVC[i] == 0) {
            printf("3\n");
            continue;
        }
        if(leftMVC[i] == 0 && rightMVC[i] == 1) {
            printf("1\n");
            continue;
        }
        if(leftMVC[i] == 1 && rightMVC[i] == 0) {
            printf("2\n");
            continue;
        }
        printf("0\n");
    }
    return 0;
}