#include <bits/stdc++.h>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int NMAX = 8205;
int L[NMAX],R[NMAX],n,m,x,y;
vector <int> v[NMAX];
bool ver[NMAX],ST[NMAX],DR[NMAX];
bool cuplaj(int node){
    if(ver[node]==true) return false;
    ver[node]=true;
    for(int i=0;i<v[node].size();i++){
        int vecin=v[node][i];
        if(R[vecin]==0){
            R[vecin]=node;
            L[node]=vecin;
            return true;
        }
    }
    for(int i=0;i<v[node].size();i++){
        int vecin=v[node][i];
        if(cuplaj(R[vecin])==true){
            R[vecin]=node;
            L[node]=vecin;
            return true;
        }
    }
    return false;
}
void mvc_dfs(int nod_st){
    ST[nod_st]=false;
    ver[nod_st]=true;
    for(int i=0;i<v[nod_st].size();i++){
       int vecin=v[nod_st][i];
       if(ver[R[vecin]]==true) continue;
       DR[vecin]=true;
       mvc_dfs(R[vecin]);
    }
}
int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++){
        fin >> x >> y;
        v[x].push_back(y);
    }
    bool ok=true;
    int rasp=0;
    while(ok==true){
        ok=false;
        for(int i=0;i<=8200;i++) ver[i]=false;
        for(int i=1;i<=n;i++){
            if(L[i]==false and cuplaj(i)==true){
                rasp++;
                ok=true;
            }
        }
    }
    fout << 2*n-rasp << '\n';
    for(int i=1;i<=n;i++){
        if(L[i]!=0){
            ST[i]=true;
            ver[i]=false;
        }
    }
    for(int i=1;i<=n;i++)
        if(L[i]==0)
            mvc_dfs(i);
    for(int i=1;i<=n;i++){
        if(ST[i]==true and DR[i]==true)   fout << 0 << '\n';
        if(ST[i]==false and DR[i]==true)  fout << 1 << '\n';
        if(ST[i]==true and DR[i]==false)  fout << 2 << '\n';
        if(ST[i]==false and DR[i]==false) fout << 3 << '\n';
    }
    return 0;
}