#include <fstream>
#include <vector>
#include <cstring>
#define DIM 9000
using namespace std;

ifstream in("felinare.in");
ofstream out("felinare.out");

int felinare, n, m, first[DIM], second[DIM], r_match[DIM], l_match[DIM], vis[DIM], sl[DIM], sr[DIM];

vector <int> edges[DIM];

bool cupleaza(int nod){
    int neigh;
    if(vis[nod]) return false;
    vis[nod]=1;
    for(int i=0; i<edges[nod].size(); ++i){
        neigh=edges[nod][i];
        if(!r_match[neigh]){
            r_match[neigh]=nod;
            l_match[nod]=neigh;
            return true;
        }
    }
    for(int i=0; i<edges[nod].size(); ++i){
        neigh=edges[nod][i];
        if(cupleaza(r_match[neigh])){
            r_match[neigh]=nod;
            l_match[nod]=neigh;
            return true;
        }
    }
    return false;
}

void build_matching(){
    int temp=1;
    while(temp){
        temp=0;
        memset(vis, 0, sizeof(vis));
        for(int i=1; i<=n; ++i){
            if(!l_match[i]&&cupleaza(i)){
                felinare--, temp=1;
            }
        }
    }
}

void suport(int vf){
    for(int j=0; j<edges[vf].size(); ++j){
        if(!sr[edges[vf][j]]){
            sr[edges[vf][j]]=2;
            sl[r_match[edges[vf][j]]]=0;
            suport(r_match[edges[vf][j]]);
        }
    }
}

int main()
{
    int a, b;
    in>>n>>m;
    while(m--){
        in>>a>>b;
        first[a]++;
        second[b]++;
        edges[a].push_back(b);
    }
    felinare=2*n;
    build_matching();
    out<<felinare<<"\n";
    for(int i=1; i<=n; ++i){
        if(l_match[i])
            sl[i]=1;
    }
    for(int i=1; i<=n; ++i){
        if(!l_match[i])
            suport(i);
    }
    for(int i=1; i<=n; ++i){
        out<<3-sl[i]-sr[i]<<"\n";
    }
    in.close();
    out.close();
    return 0;
}