#pragma GCC optimize ("-O3")
#include <fstream>
#include <vector>
#include <bitset>
int n,m,l[8192],r[8192],cnt;
std::vector<int>G[8192];
std::bitset<8192>v,fin,fout;
bool cuplaj(int nod)
{
    if(v[nod]==1)return 0;
    v[nod]=1;
    for(auto &it:G[nod])
        if(r[it]==0)
        {
            l[nod]=it;
            r[it]=nod;
            return 1;
        }
    for(auto &it:G[nod])
        if(cuplaj(r[it]))
        {
            l[nod]=it;
            r[it]=nod;
            return 1;
        }
    return 0;
}
void dfs(int nod)
{
    for(auto &it:G[nod])
        if(fin[it]==1)fin[it]=0,dfs(r[it]);
}
int main()
{
    std::ios::sync_with_stdio(0);
    std::ifstream f("felinare.in");f.tie(0);
    f>>n>>m;
    while(m--)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
    }
    f.close();
    while(1)
    {
        bool ch=0;
        v.reset();
        for(int i=1;i<=n;i++)
            if(!l[i])ch|=cuplaj(i);
        if(!ch)break;
    }
    for(int i=1;i<=n;i++)
    {
        if(l[i]>0)cnt++;
        fin[i]=fout[i]=1;
    }
    for(int i=1;i<=n;i++)
        if(l[i]==0)dfs(i);
    for(int i=1;i<=n;i++)
        if(l[i]!=0&&fin[l[i]]==1)fout[i]=0;
    std::ofstream g("felinare.out");g.tie(0);
    g<<2*n-cnt<<"\n";
    for(int i=1;i<=n;i++)
        if(fin[i]==1&&fout[i]==1)g<<3<<"\n";
        else if(fin[i]==1&&fout[i]==0)g<<2<<"\n";
        else if(fin[i]==0&&fout[i]==1)g<<1<<"\n";
        else if(fin[i]==0&&fout[i]==0)g<<0<<"\n";
    g.close();
    return 0;
}