#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;
vector<bool> ADJ[MAXN];
var n;

var nodes[4];
inline bool res() {
    for(var i=0; i<4; i++) {
        for(var j=i+1; j<4; j++) {
            if(!ADJ[nodes[i]][nodes[j]])
                return 0;
        }
    }
    return 1;
}

int main() {
    var m, a, b;
    fin>>n>>m;
    for(var i=1; i<=n; i++) {
        ADJ[i].resize(n+1, 0);
    }
    for(var i=1; i<=m; i++) {
        fin>>a>>b;
        EDGES.push_back(Edge(a, b));
        ADJ[a][b] = 1;
        ADJ[b][a] = 1;
    }

    var cnt3 = 0;

    for(auto e: EDGES) {
        for(var i=1; i<=n; i++) {
            if(ADJ[e.n1][i] && ADJ[e.n2][i]) {
                cnt3 ++;
            }
        }
    }

    var cnt4 = 0;
    for(var i=0; i<EDGES.size(); i++) {
        for(var j=i+1; j<EDGES.size(); j++) {
                Edge &e = EDGES[i];
                Edge &f = EDGES[j];
            if(e.n1 != f.n1 && e.n2 != f.n2 && e.n1 != f.n2 && e.n2 != f.n1) {
                nodes[0] = e.n1;
                nodes[1] = e.n2;
                nodes[2] = f.n1;
                nodes[3] = f.n2;
                cnt4 += res();
            }
        }
    }

    if(cnt4 > 0) {
        fout<<"4 "<<cnt4/3;
    } else if(cnt3 > 0) {
        fout<<"3 "<<cnt3/3;
    } else {
        fout<<"2 "<<m;
    }


    return 0;
}