#include<bits/stdc++.h>
#define inf INT_MAX-1
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int const N = 2e4 + 3;
int n , m , a , b;
int st[N] , dr[N] , lv[N] , off[N];
vector<int> v[N];
queue<int> q;
bool bfs(){
    for(int i = 1 ; i <= n ; ++ i)
        if(!dr[i])
            q.push(i) , lv[i] = 0;
        else
            lv[i] = inf;
    lv[0] = inf;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(lv[x] < lv[0]){
            for(auto y : v[x]){
                if(lv[st[y]] == inf){
                    lv[st[y]] = 1 + lv[x];
                    q.push(st[y]);
                }
            }
        }
    }
    return lv[0] != inf;
}
bool dfs(int x){
    if(x != 0){
        for(auto y : v[x]){
            if(lv[st[y]] == 1 + lv[x] && dfs(st[y])){
                dr[x] = y;
                st[y] = x;
                return true;
            }
        }
        lv[x] = inf;
        return false;
    }
    return true;
}
void maxmatch(){
    fill(st , st + N , 0);
    fill(dr , dr + N , 0);
    int r = 0 ;
    while(bfs()){
        for(int i = 1 ; i <= n ; ++ i){
            if(!dr[i] && dfs(i))
                ++ r;
        }
    }
}
void repair(int x){
    for(auto y : v[x]){
        if(off[y])
            continue;
        off[y] = 1;
        off[st[y]] = 0;
        repair(st[y]);
    }
}
int main(){
    fin >> n >> m;
    for(int i = 1 ; i <= m ; ++ i){
        fin >> a >> b;
        v[a].push_back(b + n);
    }
    maxmatch();
    int r = n + n;
    for(int i = 1 ; i <= n ; ++ i)
        if(dr[i]){
            -- r;
            off[i] = 1;
        }
    ///nodurile cuplate sunt ok
    for(int i = 1 ; i <= n ; ++ i){
        if(!dr[i])///nodurile necuplate
            repair(i);
    }
    fout << r << '\n';
    for(int i = 1 ; i <= n ; ++ i)
        fout << 1 - off[i] + (off[i + n] ? 0 : 2) << '\n';
    return 0;
}