#include <fstream>
#include <vector>
#include<set>
#define DIM 30001
using namespace std;
ifstream fin("count.in");
ofstream fout("count.out");
set<int> s[DIM];
set<int>::iterator it1,it2,it3;
int i,j,n,m,a,b,aux,nod,sol3,sol4,v[5],f[DIM];
vector<int> c;
int verifica(int nr)
{
    int ok=1,i,j;
    for(i=1;i<=nr;i++)
        for(j=1;j<=nr;j++)if(j!=i)
            if(s[v[i]].find(v[j])==s[v[i]].end()) ok=0;

    return ok;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        s[a].insert(b);s[b].insert(a);
    }
    for(i=1;i<=n;i++) if(s[i].size()<=5) c.push_back(i);
    while(!c.empty())
    {
        nod=c.back();c.pop_back();f[nod]=1;
        for(it1=s[nod].begin();it1!=s[nod].end();it1++)
            for(it2=it1;it2!=s[nod].end();it2++)if(it1!=it2)
            {
                v[1]=nod;v[2]=*it1;v[3]=*it2;
                sol3+=verifica(3);
            }
        for(it1=s[nod].begin();it1!=s[nod].end();it1++)
            for(it2=it1;it2!=s[nod].end();it2++)
                for(it3=it2;it3!=s[nod].end();it3++)if(it1!=it2&&it2!=it3&&it3!=it1)
                {
                    v[1]=nod;v[2]=*it1;v[3]=*it2;v[4]=*it3;
                    sol4+=verifica(4);
                }
        for(it1=s[nod].begin();it1!=s[nod].end();it1++)
        {aux=*it1;s[aux].erase(nod);if(s[aux].size()<=5&&f[aux]==0){c.push_back(aux);f[aux]=1;}}
    }
    if(sol4) fout<<4<<" "<<sol4;
    else if(sol3) fout<<3<<" "<<sol3;
    else if(m) fout<<2<<" "<<m;
    else fout<<1<<" "<<n;
    return 0;
}