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

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

const int MAX_N = 30100;

unordered_set<int> A[MAX_N];
vector<int> G[MAX_N];

bool iscl(int a, int b, int c) {
    return A[a].count(b) && A[a].count(c) && A[b].count(c);
}

bool iscl(int a, int b, int c, int d) {
    return A[a].count(a) && A[a].count(b) && A[a].count(d) && A[b].count(c) && A[b].count(d) && A[c].count(d);
}

void graf(int n) {
    for(int i = 1; i <= n; i++) {
        A[i].clear();
        for(auto it : G[i]) {
            A[i].insert(it);
        }
    }
}

int countcl4(int nod) {
    int ans = 0;
    for(auto it1 = A[nod].begin(); it1 != A[nod].end(); it1++) {
        auto it2 = it1;
        for(++it2; it2 != A[nod].end(); it2++) {
            auto it3 = it2;
            for(++it3; it3 != A[nod].end(); it3++) {
                if(iscl(nod, *it1, *it2, *it3)) {
                    ans++;
                }
            }
        }
    }
    return ans;
}

int countcl3(int nod) {
    int ans = 0;
    for(auto it1 = A[nod].begin(); it1 != A[nod].end(); it1++) {
        auto it2 = it1;
        for(++it2; it2 != A[nod].end(); it2++) {
            if(iscl(nod, *it1, *it2)) {
                ans++;
            }
        }
    }
    return ans;
}

int countcl(int n, int val) {
    graf(n);
    queue<int> Q;
    for(int i = 1; i <= n; i++) {
        if(A[i].size() <= 5) {
            Q.push(i);
        }
    }

    int ans = 0;

    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();

        if((int)A[nod].size() >= val - 1) {
            if(val == 4) {
                ans += countcl4(nod);
            }
            else {
                ans += countcl3(nod);
            }
        }

        for(auto it :  A[nod]) {
            A[it].erase(nod);
            if(A[it].size() <= 5) {
                Q.push(it);
            }
        }
        A[nod].clear();
    }

    return ans;
}

int main() {
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int x = countcl(n, 4);
    if(x) {
        fout << 4 << ' ' << x;
        return 0;
    }
    x = countcl(n, 3);
    if(x) {
        fout << 3 << ' ' << x;
        return 0;
    }
    fout << 2 << ' ' << m;
    return 0;
}