#include <bits/stdc++.h>

using namespace std;

ifstream f("count.in");
ofstream g("count.out");

const int NMAX = 30005;

int n, m;
int clq[5];
set <int> G[NMAX];

class Cp {
    public:
        inline bool operator () (int i, int j) {
            return G[i].size() < G[j].size();
        }
};

multiset <int, Cp> s;

void findCliques(vector <int> &v) {
    int size = v.size();
    for (int i = 1; i < (1 << size); i++) {
        bool is_clq = true;
        for (int j = 0; is_clq == true && j < size; j++) {
            for (int k = j + 1; is_clq == true && k < size; k++) {
                if (((i >> j) & 1) == true && ((i >> k) & 1) == true) {
                    is_clq &= (G[v[j]].find(v[k]) != G[v[j]].end() &&
                               G[v[k]].find(v[j]) != G[v[k]].end());
                }
            }
        }
        if (is_clq == true) {
            clq[__builtin_popcount(i) + 1]++;
        }
    }
}

void decPlanar() {
    for (int i = 1; i <= n; i++) {
        s.insert(i);
    }
    while (s.empty() == false) {
        int u = *s.begin();
        s.erase(s.begin());
        vector <int> c;
        while (G[u].empty() == false) {
            int v = *G[u].begin();
            s.erase(s.find(v));
            G[u].erase(G[u].begin());
            G[v].erase(G[v].find(u));
            c.push_back(v);
            s.insert(v);
        }
        findCliques(c);
    }
}

int main() {
    f >> n >> m;
    while (m--) {
        int u, v;
        f >> u >> v;
        G[u].insert(v);
        G[v].insert(u);
    }
    decPlanar();
    int k = 4;
    while (k > 0 && clq[k] == 0) {
        k--;
    }
    g << k << " " << clq[k] << "\n";
    return 0;
}