#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <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;
pair<int, int> edges[MAX_M];
vector<int> graph[MAX_N];
bool removed_edge[MAX_M];
int node_degree[MAX_N];
int max_clique[5];
queue<int> q;

void read_input();
void solve();
void print_output();
void find_max_clique();
void compute_clique(int node);
bool adjacent(int a, int b);
int other(int edge, int node);

int main() {
    read_input();
    solve();
    print_output();
    return 0;
}

void read_input() {
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        fin >> edges[i].first;
        fin >> edges[i].second;

        graph[edges[i].first].push_back(i);
        graph[edges[i].second].push_back(i);
    }
}

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() {
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        compute_clique(node);

        for (auto x: graph[node]) {
            if (removed_edge[x]) continue;
            int neighbour = other(x, node);

            removed_edge[x] = true;
            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 (removed_edge[graph[node][a]]) continue;
        max_clique[2] += 1;

        for (int b = a + 1; b < n; ++b) {
            if (removed_edge[graph[node][b]]) continue;
            if (adjacent(other(graph[node][a], node), other(graph[node][b], node))) {
                max_clique[3] += 1;

                for (int c = b + 1; c < n; ++c) {
                    if (removed_edge[graph[node][c]]) continue;
                    if ((adjacent(other(graph[node][b], node), other(graph[node][c], node))) &&
                        (adjacent(other(graph[node][a], node), other(graph[node][c], node)))) {
                        max_clique[4] += 1;
                    }
                }
            }
        }
    }
}

inline bool adjacent(int a, int b) {
    for (auto x: graph[a]) {
        if (removed_edge[x]) continue;
        if (other(x, a) == b) return true;
    }
    return false;
}

inline int other(int edge, int node) {
    return edges[edge].first + edges[edge].second - node;
}