#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

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

int n, m, ans[6];
set <int> G[30005];
queue <int> q;
vector <int> v, clica;
bool viz[30005];

bool valid()
{
    for(int i = 0; i < clica.size(); i++)
    {
        int a = clica[i];
        for(int j = i + 1; j < clica.size(); j++)
        {
            int b = clica[j];
            if(G[a].find(b) == G[a].end())
                return 0;
        }
    }
    return 1;

}

void bkt(int nod, int poz)
{
    if(poz == v.size())
    {
        if(valid())
            ans[clica.size() + 1]++;
        return;
    }
    bkt(nod, poz + 1);
    clica.push_back(v[poz]);
    bkt(nod, poz + 1);
    clica.pop_back();
}


int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G[x].insert(y);
        G[y].insert(x);
    }
    for(int i = 1; i <= n; i++)
        if(G[i].size() < 6)
        {
            q.push(i);
            viz[i] = 1;
        }
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        v.clear();
        for(int vecin : G[nod])
            v.push_back(vecin);
        bkt(nod, 0);
        for(int vecin : G[nod])
        {
            auto x = G[vecin].find(nod);
            G[vecin].erase(x);
        }
        for(int vecin : G[nod])
        {
            if(G[vecin].size() < 6 && !viz[vecin])
            {
                q.push(vecin);
                viz[vecin] = 1;
            }
        }
        G[nod].clear();
    }
    for(int i = 4; i >= 2; i--)
    {
        if(ans[i])
        {
            fout << i << ' ' << ans[i];
            return 0;
        }
    }
    return 0;
}