#include <bits/stdc++.h>
#define DIM 30000
using namespace std;

ifstream fin ("felinare.in");
ofstream fout ("felinare.out");
int Left[DIM],Right[DIM],viz[DIM],g_int[DIM],g_ext[DIM],f[DIM];
vector <int> sol[DIM],L[DIM];
int n,m,i,x,y,ok,ans;
int cupleaza (int nod){
    if (viz[nod])
        return 0;
    viz[nod] = 1;
    for (auto vecin : L[nod]){
        if (!Right[vecin]){
            Right[vecin] = nod;
            Left[nod] = vecin;
            ans++;
            return 1;
        }}
    for (auto vecin : L[nod]){
        if (cupleaza(Right[vecin])){
            Right[vecin] = nod;
            Left[nod] = vecin;
            return 1;
        }}
    return 0;
}
int main (){

    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x>>y;
        L[x].push_back(y+n);
        g_ext[x]++, g_int[y]++;
    }

    do{
        memset (viz,0,sizeof viz);
        ok = 0;
        for (i=1;i<=n;i++)
            if (!Left[i] && cupleaza(i))
                ok = 1;
    } while (ok);

    for (i=1;i<=n;i++){
        if (!Left[i]){
            sol[i].push_back(1);
            f[Left[i]-n] = 1;
        }
    }
    for (i=1;i<=n;i++)
        if (!f[i])
            sol[i].push_back(2);


    fout<<2*n-ans<<"\n";
    for (i=1;i<=n;i++){
        if (sol[i].empty())
            fout<<"0\n";
        else {
            if (sol[i].size() == 2)
                fout<<"3\n";
            else fout<<sol[i][0]<<"\n";
        }
    }


    return 0;
}