#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>

#define x first
#define y second
#define NMAX 30007

using namespace std;

set < pair < int, int > > S;
set < pair < int, int > > Edges;
vector < int > v[NMAX];
int Deg[NMAX], Viz[NMAX];
int Clique3, Clique4;
int n, m;

inline bool IsClique3(int a,int b,int c){
    return Edges.count(make_pair(a, b)) && Edges.count(make_pair(a,c)) && Edges.count(make_pair(b,c));
}
inline bool IsClique4(int a,int b,int c,int d){
    return IsClique3(a, b, c) && IsClique3(a, b, d) && IsClique3(b, c, d);
}

void Cliques3(const vector < int > &v){
    for(int i = 0; i + 2 < v.size(); ++i)
        for(int j = i + 1; j + 1 < v.size(); ++j)
            for(int k = j + 1; k < v.size(); ++k)
                if(IsClique3(v[i], v[j], v[k]))
                    ++Clique3;
}
void Cliques4(const vector<int> &v){
    for(int i = 0; i + 3 < v.size(); ++i)
        for(int j = i + 1; j + 2 < v.size(); ++j)
            for(int k = j + 1; k + 1 < v.size(); ++k)
                for(int l = k + 1; l < v.size(); ++l)
                    if(IsClique4(v[i], v[j], v[k], v[l]))
                        ++Clique4;
}

void solve(){
    int x = n;
    while(x > 2){
        int Nod = S.begin()->y;
        S.erase(S.find(make_pair(Deg[Nod], Nod)));
        Deg[Nod] = Viz[Nod] = 0;
        vector < int > Sol;
        Sol.clear();
        Sol.push_back(Nod);
        for(int i = 0; i < v[Nod].size(); ++i)
            if(Viz[v[Nod][i]] == 1)
                Sol.push_back(v[Nod][i]);
        Cliques3(Sol);
        Cliques4(Sol);
        for(int i = 0; i < v[Nod].size(); ++i)
            if(Viz[v[Nod][i]] == 1){
                S.erase(S.find(make_pair(Deg[v[Nod][i]], v[Nod][i])));
                --Deg[v[Nod][i]];
                S.insert(make_pair(Deg[v[Nod][i]], v[Nod][i]));
            }
        --x;
    }
}

int main(){
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
        Edges.insert(make_pair(a, b));
        Edges.insert(make_pair(b, a));
        ++Deg[a];
        ++Deg[b];
    }
    for(int i = 1; i <= n; ++i){
        S.insert(make_pair(Deg[i], i));
        Viz[i] = 1;
    }
    solve();
    if(Clique4 != 0)
        printf("4 %d\n", Clique4);
    else
        if(Clique3 != 0)
            printf("3 %d\n", Clique3);
        else
            printf("2 %d\n", m);
    return 0;
}