#include<fstream>
#include<vector>
#include<map>
#include<unordered_map>

using namespace std;
typedef int var;

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

struct Edge {
    var n1, n2;
    Edge(var a, var b) {
        n1 = a;
        n2 = b;
    }
};

#define MAXN 30001

vector<Edge> EDGES;
map<var, bool> ADJ[MAXN];
var n;
vector<bool> VIZ(MAXN);
vector<var> G[MAXN];
var D[MAXN];

var nodes[4];
var sol_3, sol_4;

bool check_3 (var n1, var n2, var n3) {
    if(VIZ[n1] | VIZ[n2] | VIZ[n3]) return 0;
    if((n1-n2)*(n2-n3)*(n3-n1) == 0) return 0;
    if(ADJ[n1][n2] & ADJ[n2][n3] & ADJ[n3][n1]) return 1;
    return 0;
}

bool check_4 (var n1, var n2, var n3, var n4) {
    if(VIZ[n4]) return 0;
    //if(!check_3(n1, n2, n3)) return 0;
    if(!((n1-n4)*(n2-n4)*(n3-n4))) return 0;
    if(ADJ[n4][n1] & ADJ[n4][n2] & ADJ[n4][n3]) return 1;
    return 0;
}


void check(var node) {
    typedef map<var, bool>::iterator itt;
    for(var i=0; i<G[node].size(); i++) {
        var n1 = G[node][i];
        if(VIZ[n1]) continue;
        for(var j=i+1; j<G[node].size(); j++) {
            var n2 = G[node][j];
            if(VIZ[n2]) continue;
            if(check_3(node, n1, n2)) {
                sol_3 ++;
                for(var k=j+1; k<G[node].size(); k++) {
                    var n3 = G[node][k];
                    if(VIZ[n3]) continue;
                    sol_4 += check_4(node, n1, n2, n3);
                }
            }
        }
    }

    VIZ[node] = 1;
    for(auto vec: G[node]) {
        ADJ[vec].erase(node);
        D[vec]--;
    }
    for(auto vec: G[node]) {
        if(D[vec] <= 6 && !VIZ[vec]) {
            check(vec);
        }
    }
    ADJ[node].clear();
}


int main() {
    var m, a, b;
    fin>>n>>m;

    for(var i=1; i<=m; i++) {
        fin>>a>>b;
        D[a]++;
        D[b]++;
        G[a].push_back(b);
        G[b].push_back(a);
        ADJ[a][b] = 1;
        ADJ[b][a] = 1;
    }

    for(var i=1; i<=n; i++) {
        if(!VIZ[i] && D[i] <= 6) {
            check(i);
        }
    }

    if(sol_4 > 0) {
        fout<<"4 "<<sol_4;
    } else if(sol_3 > 0) {
        fout<<"3 "<<sol_3;
    } else {
        fout<<"2 "<<m;
    }


    return 0;
}