#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],f[DIM],L[DIM],R[DIM];
vector <int> sol[DIM],edg[DIM];
int n,m,i,x,y,ok,ans;
int cupleaza (int nod){
    if (viz[nod])
        return 0;
    viz[nod] = 1;
    for (auto vecin : edg[nod]){
        if (!Right[vecin]){
            Right[vecin] = nod;
            Left[nod] = vecin;
            L[nod] = 1;
            ans++;
            return 1;
        }}
    for (auto vecin : edg[nod]){
        if (cupleaza(Right[vecin])){
            Right[vecin] = nod;
            Left[nod] = vecin;
            L[nod] = 1;
            return 1;
        }}
    return 0;
}
void dfs (int nod){
    for (auto vecin : edg[nod]){
        if (!R[vecin]){
            R[vecin] = 1;
            L[nod] = 0;
            dfs (Right[vecin]);
        }}
}
int main (){

    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x>>y;
        edg[x].push_back(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 (!L[i])
            dfs (i);


    fout<<2*n-ans<<"\n";
    for (i=1;i<=n;i++){
        if (L[i] && R[i])
            ok = 0;
        if (!L[i] && !R[i])
            ok = 3;
        if (L[i] && !R[i])
            ok = 2;
        if (!L[i] && R[i])
            ok = 1;

        fout<<ok<<"\n";
    }


    return 0;
}