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

int main() {
    var m, a, b;
    fin>>n>>m;
    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 cnt = 0;

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

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


    return 0;
}