#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int nod, nr, ans, sol, n, m, grad[30009], ap[30009], v[1000], x[1000];
vector < int > V[30009];

map < int , bool > mp[30009];

class MyClass
{
    public:
    bool operator () (const pair < int , int > &a, const pair < int , int > &b) const
    {
        return a.first > b.first;
    }
};

priority_queue < pair < int , int > , vector < pair < int , int > > , MyClass > Mp;

void back (int poz)
{
    if (poz > ans)
        ans = poz , sol=1;
    else
    if (poz == ans)
        sol++;
    for (int i=x[poz-1] + 1; i<=nr; i++)
    {
        int j;
        for (j=1; j<poz; j++)
            if (mp[v[i]][v[x[j]]] != 1) break;
        if (j == poz)
        {
            x[poz] = i;
            back (poz+1);
        }
    }
}

void dfs()
{
    bool ok = 0;
    pair < int , int > ceva;
    while (1)
    {
        if (Mp.empty()) break;
        ceva = Mp.top();
        Mp.pop();
        if (grad[ceva.second]!=ceva.first) ;
        else
        {
            ok = 1;
            break;
        }
    }
    if (ok == 0) return ;
    nod = ceva.second;
    nr = 0;
    for (vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); it++)
    if (ap[*it] == 0)
    {
        v[++nr] = *it;
        grad[*it] -- ;
        Mp.push(make_pair(grad[*it], *it));

    }
    back (1);
    ap[nod] = 1;
    dfs ();
}

int main()
{
freopen ("count.in", "r", stdin);
freopen ("count.out", "w", stdout);
scanf ("%d%d", &n, &m);
if (m == 0)
{
    printf ("1 %d\n", n);
    return 0;
}
while (m)
{
    m--;
    int X, Y;
    scanf ("%d %d", &X, &Y);
    V[X].push_back(Y);
    V[Y].push_back(X);
    grad[X]++;
    grad[Y]++;
    mp[X][Y]=1;
    mp[Y][X]=1 ;
}
//printf ("%d\n", mp[2][5]);
//return 0;
for (int i=1; i<=n; i++)
    Mp.push(make_pair(grad[i], i));
dfs ();
printf ("%d %d\n", ans, sol);
return 0;
}