#include <fstream>
#include <deque>
#include <set>
#define DIM 30010
using namespace std;

ifstream fin ("count.in");
ofstream fout ("count.out");
set <int> L[DIM];
int g[DIM],v[6],clc[6],f[DIM];
deque <int> c;
int n,m,nod,i,x,y,z,j,t,k;
int main (){

    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x>>y;
        g[x]++, g[y]++;
        L[x].insert(y);
        L[y].insert(x);
        clc[2]++;
    }
    for (i=1;i<=n;i++)
        if (g[i] <= 5){
            c.push_back (i);
            f[i] = 1;
        }

    while (!c.empty()){
        nod = c.front();
        /// vreau sa numar din cate clici de 3 si de 4 face parte nod
        k = 0;
        for (set<int>::iterator it=L[nod].begin();it!=L[nod].end();it++)
            v[++k] = *it;
        /// clica de lg 3
        for (i=1;i<k;i++)
            for (j=i+1;j<=k;j++){ /// vreau sa vad daca am muchie intre astea doua
                x = v[i], y = v[j];
                if (L[x].find(y) != L[x].end()) /// l am gasit deci am  clica de lg 3
                    clc[3]++;
            }
        /// clica de lg 4
        for (i=1;i<k-1;i++)
            for (j=i+1;j<k;j++)
                for (t=j+1;t<=k;t++){
                    x = v[i], y = v[j], z = v[t];
                    if (L[x].find(y)!=L[x].end()&& L[x].find(z)!=L[x].end() && L[y].find(z)!=L[y].end())
                        clc[4]++;
                }
        /// trebuie sa elimin nodul
        c.pop_front();
        for (i=1;i<=k;i++){
            g[v[i]]--;
            if (g[v[i]] <= 5 && !f[v[i]]){
                f[v[i]] = 1;
                c.push_back (v[i]);
            }
            L[v[i]].erase(L[v[i]].find(nod)); /// sterg muchia catre nod
        }
    }

    if (clc[4]){
        fout<<4<<" "<<clc[4];
        return 0;
    }
    if (clc[3]){
        fout<<3<<" "<<clc[3];
        return 0;
    }
    if (clc[2]){
        fout<<2<<" "<<clc[2];
        return 0;
    }
    if (clc[1])
        fout<<1<<" "<<clc[1];




    return 0;
}