#include <bits/stdc++.h>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int NMAX=8200;

int n,l[NMAX],r[NMAX],sol;
bool used[NMAX],dr[NMAX];
vector <int> g[NMAX];

void read();
void dfs(int);
bool match(int);

int main(){
    read();
    int ok=1;
    while(ok){
        memset(used, 0, sizeof used);
        ok=0;
        for(int i=1;i<=n;++i){
            if(!used[i] && !l[i])
                ok+=match(i);
        }
        sol+=ok;
    }
    memset(used, 0, sizeof used);
    for(int i=1;i<=n;++i){
        if(!l[i]&&!used[i])
            dfs(i);
    }
    fout<<2*n - sol<<'\n';
    for(int i=1;i<=n;++i){
        fout<<3-(!used[i])-(2*dr[i])<<'\n';
    }
}
bool match(int node){
    used[node]=1;
    for(auto it:g[node]){
        if(!r[it] || (!used[r[it]] && match(r[it]))){
            l[node]=it;
            r[it]=node;
            return 1;
        }
    }
    return 0;
}
void dfs(int node){
    used[node]=1;
    for(auto it:g[node]){
        if(!used[r[it]] && r[it])
            dfs(r[it]);
    }
}
void read(){
    int m,x,y;
    fin>>n>>m;
    for(int i=0;i<m;++i){
        fin>>x>>y;
        g[x].push_back(y);
    }
}