#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <vector>
using namespace std;
 
ifstream fin("count.in");
ofstream fout("count.out");
 
const int MAX_N = 30100;
const int MAX_M = 60100;
 
int N, M;
vector<int> graph[MAX_N];
int node_degree[MAX_N];
int max_clique[5];
queue<int> q;
 
set<pair<int, int>> edges;
 
void read_input();
void solve();
void print_output();
void find_max_clique();
void compute_clique(int node);
bool adjacent(int a, int b);
 
int main() {
    read_input();
    solve();
    print_output();
    return 0;
}
 
void read_input() {
    fin >> N >> M;
    for (int i = 1, a, b; i <= M; ++i) {
        fin >> a >> b;
 
        graph[a].push_back(b);
        graph[b].push_back(a);
        edges.insert(make_pair(a, b));
    }
}
 
void solve() {
    for (int i = 1; i <= N; ++i) {
        node_degree[i] = graph[i].size();
        if (node_degree[i] < 6) {
            q.push(i);
        }
    }
 
    max_clique[1] = N;
    find_max_clique();
}
 
void print_output() {
    for (int i = 4; i > 0; i -= 1) {
        if (max_clique[i]) {
            fout << i << ' ' << max_clique[i];
            return;
        }
    }
}
 
void find_max_clique() {
    set<pair<int, int>>::iterator it;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        compute_clique(node);
 
        for (auto neighbour: graph[node]) {
            it = edges.find(make_pair(node, neighbour));
            if (it == edges.end()) it = edges.find(make_pair(neighbour, node));
            if (it == edges.end()) continue;
 
            edges.erase(it);
            node_degree[neighbour] -= 1;
            if (node_degree[neighbour] == 5) {
                q.push(neighbour);
            }
        }
    }
}
 
void compute_clique(int node) {
    int n = graph[node].size();
 
    for (int a = 0; a < n; ++a) {
        if (!adjacent(node, graph[node][a])) continue;
        max_clique[2] += 1;
 
        for (int b = a + 1; b < n; ++b) {
            if (!adjacent(node, graph[node][b])) continue;
            if (adjacent(graph[node][a], graph[node][b])) {
                max_clique[3] += 1;
 
                for (int c = b + 1; c < n; ++c) {
                    if (!adjacent(node, graph[node][c])) continue;
                    if ((adjacent(graph[node][b], graph[node][c])) &&
                        (adjacent(graph[node][a], graph[node][c]))) {
                        max_clique[4] += 1;
                    }
                }
            }
        }
    }
}
 
inline bool adjacent(int a, int b) {
    if (edges.find(make_pair(a, b)) != edges.end()) return true;
    return (edges.find(make_pair(b, a)) != edges.end());
}