#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream f("count.in");
ofstream g("count.out");
int N,M;
vector <int> G[30005];
set <pair<int,int> > Set;
set <int> Set2[30005];
int Grade[30005],res,nb;
void Read()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y;
        f>>x>>y;
        Set2[x].insert(y);
        Set2[y].insert(x);
        Grade[x]++;Grade[y]++;
    }
    for(int i=1;i<=N;i++)
        Set.insert(make_pair(Grade[i],i));
}

void Solve3()
{
    int nodes=N,current;
    while(nodes>0)
    {
        current=(*Set.begin()).second;
        Set.erase(Set.begin());
        auto it=Set2[current].begin();
        if(Set2[current].size()>=2)
        for(;it!=prev(Set2[current].end());it++)
        {
            for(auto it2=next(it);it2!=Set2[current].end();it2++)
            {
                if(Set2[*it].find(*it2)!=Set2[*it].end())
                    ++nb;
            }
        }
        for(auto it=Set2[current].begin();it!=Set2[current].end();it++)
        {
            int neighb=*it;
            Set2[neighb].erase(current);
            --Grade[neighb];
            Set.erase(make_pair(Grade[neighb]+1,neighb));
            Set.insert(make_pair(Grade[neighb],neighb));
        }
        --nodes;
    }
}

void Solve4()
{
    int nodes=N,current;
    while(nodes>0)
    {
        current=(*Set.begin()).second;
        Set.erase(Set.begin());
        auto it=Set2[current].begin();
        if(Set2[current].size()>=3)
        for(;it!=prev(prev(Set2[current].end()));it++)
        {
            for(auto it2=next(it);it2!=prev(Set2[current].end());it2++)
            {
                if(Set2[*it].find(*it2)!=Set2[*it].end())
                {
                    for(auto it3=next(it2);it3!=Set2[current].end();it3++)
                        if(Set2[*it].find(*it3)!=Set2[*it].end() && Set2[*it2].find(*it3)!=Set2[*it2].end())
                            ++nb;
                }
            }
        }
        for(auto it=Set2[current].begin();it!=Set2[current].end();it++)
        {
            int neighb=*it;
            Set2[neighb].erase(current);
            --Grade[neighb];
            Set.erase(make_pair(Grade[neighb]+1,neighb));
            Set.insert(make_pair(Grade[neighb],neighb));
        }
        --nodes;
    }
}
int main()
{
    Read();
    Solve4();
    res=4;
    if(nb==0)
    {
        for(int i=1;i<=N;i++)
        {
            Grade[i]=0;
            Set2[i].clear();
        }
        Set.clear();
        res=3;
        f.close();
        f.open("count.in");
        Read();
        Solve3();
    }
    if(nb==0)
        res=0;
    g<<res<<" "<<nb<<"\n";
    return 0;
}