#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
int n,m,i,j,l[17010],x,y,sol;
vector<int>a[17010];
bool ok,uz[17010];
int cupleaza(int x)
{
    int i;
    if(uz[x])
    return 0;
    uz[x]=1;
    for(i=0;i<a[x].size();++i)
    if(!l[a[x][i]])
    {
        l[x]=a[x][i];
        l[a[x][i]]=x;
        return 1;
    }

    for(i=0;i<a[x].size();++i)
    if(cupleaza(l[a[x][i]]))
    {
        l[x]=a[x][i];
        l[a[x][i]]=x;
        return 1;
    }
    return 0;
}
void df(int x)
{
    for(int i=0;i<a[x].size();++i)
    if(!uz[a[x][i]])
    {
        uz[a[x][i]]=1;
        uz[l[a[x][i]]]=0;
        df(a[x][i]);
    }
}
int main()
{
    ifstream f("felinare.in");
    ofstream g("felinare.out");
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        a[x].push_back(y+n);
    }
    ok=0;
    sol=2*n;
    while(!ok)
    {
        memset(uz,0,sizeof(uz));
        ok=1;
        for(i=1;i<=n&&!ok;++i)
        if(!l[i]&&cupleaza(i))
        ok=0;
    }

    memset(uz,0,sizeof(uz));
    for(i=1;i<=n;++i)
    {
        if(l[i])
        uz[i]=1;
        else
        df(i);
    }
    sol=2*n;
    for(i=1;i<=n;++i)
    if(uz[i])
    --sol;
    g<<sol<<'\n';
    for(i=1;i<=n;++i)
    if(!uz[i]&&!uz[n+i])
    g<<3<<'\n';
    else
    if(uz[i]&&!uz[i+n])
    g<<2<<'\n';
    else
    if(!uz[i]&&uz[i+n])
    g<<1<<'\n';
    else
    g<<0<<'\n';



}