#include<fstream>
#include<iostream>
#include<vector>
#define DN 8205
#define pb push_back
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int n,m,f,g,c1[DN],c2[DN],p,viz[4*DN],nr,st[4*DN],top,poz1,poz2;
int rez[4*DN],k,f1[DN],f2[DN];
vector<int>v[4*DN];
vector<int>r[4*DN];
int ve1(int nod)
{
    if(viz[nod])
        return 0;
    viz[nod]=1;
    for(auto i:v[nod])
        if(!c2[i]||ve1(c2[i]))
        {
            c1[nod]=i;
            c2[i]=nod;
            return 1;
        }
    return 0;
}
void ve2(int nod)
{
    for(auto i:v[nod])
        if(!f2[i])
        {
            f2[i]=1;
            f1[c2[i]]=0;
            ve2(c2[i]);
        }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>f>>g;
        v[f].pb(g);
    }
    p=1;
    while(p)
    {
        p=0;
        for(int i=1;i<=n;i++)
            viz[i]=0;
        for(int i=1;i<=n;i++)
            if(c1[i]==0&&ve1(i))
            {
                nr++;
                p=1;
            }
    }
    for(int i=1;i<=n;i++)
        if(c1[i])
            f1[i]=1;
    fout<<2*n-nr<<'\n';
    for(int i=1;i<=n;i++)
        if(!f1[i])
            ve2(i);
    for(int i=1;i<=n;i++)
    {
        if(!f1[i]&&!f2[i])
        {
            k+=2;
            fout<<3<<'\n';
            continue;
        }
        if(!f1[i])
        {
            k++;
            fout<<1<<'\n';
            continue;
        }
        if(!f2[i])
        {
            k++;
            fout<<2<<'\n';
            continue;
        }
        fout<<0<<'\n';
    }
}