#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

ifstream in("count.in");
ofstream out("count.out");
#define FORIT(st, i, v) for(int i = st; i < int(v.size()); ++i)
const int max_n = 30005;

vector<int> vertex[max_n], v;
priority_queue <pair<int,int> > pq;
unordered_map <int,bool> mu[max_n];

int n, m;
bool viz[max_n];
int sz[max_n];
int rez[5];

void bt (int nod) {
    FORIT(0, it, v)
        FORIT(it+1, it2, v) {
            int a = nod, b = v[it], c = v[it2];
            if (mu[a][b] && mu[b][c] && mu[c][a]) {
                rez[3] ++;
                FORIT (it2+1, it3, v) {
                    int d = v[it3];
                    if (mu[a][d] && mu[d][b] && mu[d][c])
                        rez[4]++;
                }
            }
        }
}

int main() {
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        in >> a >> b;
        vertex[a].push_back(b);
        vertex[b].push_back(a);
        mu[a][b] = true;
        mu[b][a] = true;
    }
    for (int i = 1; i <= n; ++i) {
        pq.push (make_pair(-vertex[i].size(), i));
        sz[i] = vertex[i].size();
    }
    while (pq.size()) {
        int nod = pq.top().second;
        pq.pop();
        if (viz[nod])
            continue ;
        viz[nod] = true;
        v.clear();
        FORIT (0, it, vertex[nod])
            if (not viz[vertex[nod][it]])
                v.push_back(vertex[nod][it]);
        bt(nod);
        FORIT (0, it, vertex[nod]) {
            int a = vertex[nod][it];
            sz[a] --;
            pq.push(make_pair(-sz[a], a));
        }
    }
    rez[2] = m;
    for (int i = 4; i; --i)
        if (rez[i]) {
            out << i << ' ' << rez[i] << '\n';
            return 0;
        }
    return 0;
}