#include <fstream>
#include <set>
#include <queue>

using namespace std;

ifstream fin ("count.in");
ofstream fout ("count.out");

queue <int> q;

set <int> l[30010];
set <int>:: iterator iti,itj,itk;

int n,m,x,y,i,sol[5];

int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        l[x].insert(y);
        l[y].insert(x);
    }
    for (i=1;i<=n;i++)
        if (l[i].size()<6)
            q.push(i);
    while (!q.empty()){
        x=q.front();
        for (iti=l[x].begin();iti!=l[x].end();iti++)
            for (itj=l[x].begin();itj!=l[x].end();itj++)
                if (iti!=itj && l[*iti].find(*itj)!=l[*iti].end())
                    sol[3]++;
        for (iti=l[x].begin();iti!=l[x].end();iti++)
            for (itj=l[x].begin();itj!=l[x].end();itj++)
                if (iti!=itj)
                    for (itk=l[x].begin();itk!=l[x].end();itk++)
                        if (iti!=itk && l[*iti].find(*itj)!=l[*iti].end() && l[*iti].find(*itk)!=l[*iti].end()&& l[*itk].find(*itk)!=l[*itk].end())
                            sol[4]++;
        for (iti=l[x].begin();iti!=l[x].end();iti++){
            l[*iti].erase(x);
            if (l[*iti].size()==5)
                q.push(*iti);
        }
        q.pop();
    }
    sol[2]=m;
    sol[3]/=2;
    sol[4]/=6;

    for (i=4;i>=1;i--)
        if (sol[i]!=0) {
            fout<<i<<" "<<sol[i]<<"\n";
            return 0;
        }

    return 0;
}