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

using namespace std;

const int MAX_N = 8200;

vector<int> G[MAX_N];
int n,m;
bool viz[MAX_N];
int L[MAX_N], R[MAX_N];
bool taken_L[MAX_N],
     taken_R[MAX_N];

bool pair_up(const int node){
    if(viz[node])
        return false;
    viz[node] = 1;
    for(vector<int> :: iterator it = G[node].begin() ; it != G[node].end() ; ++it){
        if(!R[*it] || pair_up(R[*it])){
            L[node] = *it;
            R[*it] = node;
            return true;
        }
    }
    return false;
}

int match(){
    int ret = 0;
    bool go_on = 1;
    while(go_on){
        go_on = 0;
        for(int i = 1 ; i <= n ; ++i){
            if(!L[i] && pair_up(i)){
                ++ret;
                go_on = 1;
            }
        }
        memset(viz, 0, n + 1);
    }
    return ret;
}

void fix(const int node){
    taken_L[node] = 0;
    for(vector<int> :: iterator it = G[node].begin() ; it != G[node].end() ; ++it){
        if(!taken_R[*it]){
            taken_R[*it] = 1;
            fix(R[*it]);
        }
    }
}

int main(){
    ifstream in("felinare.in");
    in >> n >> m;
    for(int i = 0, a, b ; i < m ; ++i){
        in >> a >> b;
        G[a].push_back(b);
    }
    freopen("felinare.out", "w", stdout);
    printf("%d\n", 2 * n - match());
    for(int i = 1 ; i <= n ; ++i)
        if(L[i])
            taken_L[i] = 1;
    for(int i = 1 ; i <= n ; ++i)
        if(!taken_L[i])
            fix(i);
    for(int i = 1 ; i <= n ; ++i){
        const int type = 1 * (!taken_L[i]) + 2 * (!taken_R[i]);
        printf("%d\n", type);
    }
    return 0;
}