#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];

void countcl(int n, int &ans3, int &ans4) {
        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();

        for(auto it = A[nod].begin(); it != A[nod].end(); it++) {
            for(auto it1 = it; it1 != A[nod].end(); it1++) {
                if(it1 != it && A[*it1].count(*it)) {
                    ans3++;
                    for(auto it2 = it1; it2 != A[nod].end(); it2++) {
                        if(it2 != it1 && A[*it].count(*it2) && A[*it1].count(*it2)) {
                            ans4++;
                        }
                    }
                }
            }
        }

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

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

    int ans3 = 0;
    int ans4 = 0;

    countcl(n, ans3, ans4);

    if(ans4) {
        fout << 4 << ' ' << ans4;
    }
    else if(ans3) {
        fout << 3 << ' ' << ans3;
    }
    else if(m) {
        fout << 2 << ' ' << m;
    }
    else {
        fout << 1 << ' ' << n;
    }
    return 0;
}