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

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

bool dfs(int);
bool support(int);

int main(){
    int i,m,x,y,ok=1;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y;
        g[x].push_back(y);

    }
    while(ok){
        ok=0;
        memset(used,0,sizeof used);
        for(i=1;i<=n;++i){
            if(!used[i] && !l[i])
                ok+=dfs(i);
        }
        sol+=ok;
    }
    memset(used, 0, sizeof used);

    for(i=1;i<=n;++i){
        if(!used[i] && !l[i])
            support(i);
    }
    fout<<n*2 - sol<<'\n';
    for(i=1;i<=n;++i){
        fout<<used[i]+2*(!dr[i])<<'\n';
    }
    return 0;
}
bool support(int node){
    used[node]=1;
    for(auto it:g[node]){
        if(!used[r[it]]){
            dr[it]=1;
            dfs(r[it]);
        }
    }
}
bool dfs(int node){
    used[node]=1;
    for(auto it:g[node]){
        if(!r[it] || (!used[r[it]] && dfs(r[it]))){
            l[node]=it;
            r[it]=node;
            return 1;
        }
    }
    return 0;
}