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

set<int> L[DIMN];
int F[5];
int x[10];
int iq[DIMN], q[DIMN], D[DIMN];
int v[10];
int k, n, m, a, b, p, u;
void back(int step) {
    if (step > k) {
        int number = 0;
        for (int i=1;i<=k;i++)
            if (x[i] == 1)
                number++;
        int clica = 1;
        for (int i=1;i<=k;i++)
            for (int j=i+1;j<=k;j++)
                if (x[i] & x[j]) {
                    if (L[ v[i] ].find(v[j]) == L[v[i]].end()) {
                        clica = 0;
                        break;
                    }
                }
        if (clica)
            F[number]++;
    } else {
        for (int i=0;i<2;i++) {
            x[step] = i;
            back(step+1);
        }
    }

}

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

    fin>>n>>m;
    for (int i=1;i<=m;i++) {
        fin>>a>>b;
        L[a].insert(b);
        L[b].insert(a);
        D[a]++;
        D[b]++;
    }

    for (int i=1;i<=n;i++)
        if (D[i] < 6) {
            q[++u] = i;
            iq[i] = 1;
        }
    p = 1;
    while (p <= u) {
        int node = q[p];
        k = 1;v[1] = node;
        for (set<int>::iterator it = L[node].begin(); it != L[node].end(); it++) {
            v[++k] = *it;
        }
        back(1);
        for (set<int>::iterator it = L[node].begin(); it != L[node].end(); it++) {
            L[*it].erase(node);
            D[*it]--;
            if (D[*it] < 6 && iq[*it] == 0)
                q[++u] = *it;
        }
        p++;
    }

    if (F[4])
        fout<<"4 "<<F[4]<<"\n";
    else
        if (F[3])
            fout<<"3 "<<F[3]<<"\n";
        else
            if (F[2])
                fout<<"2 "<<F[2]<<"\n";
            else
                fout<<"1 "<<F[1]<<"\n";
    return 0;
}