#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "count";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647;

int n, m;
bool ok[2005][2005];
vector<pi> e;

int count4()
{
    int ans = 0;
    for (vector<pi>::iterator it = e.begin(); it < e.end(); ++it)
        for (vector<pi>::iterator it2 = it+1; it2 < e.end(); ++it2){
            int a = it->ff, b = it->ss, c = it2->ff, d = it2->ss;
            if(a == c || a == d || b == c || b == d)
                continue;
            if(ok[a][c] && ok[a][d] && ok[b][c] && ok[b][d])
                ++ans;
        }
    return ans;
}

int count3()
{
    int ans = 0;
    for (vector<pi>::iterator it = e.begin(); it < e.end(); ++it)
        for (int t = 1; t <= n; ++t){
            int a = it->ff, b = it->ss;
            if(a == t || b == t)
                continue;
            if(ok[a][t] && ok[b][t])
                ++ans;
        }
    return ans;
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y;
        fin >> x >> y;
        ok[x][y] = ok[y][x] = 1;
        e.push_back({min(x, y), max(x, y)});
    }
    int ans = 0;
    ans = count4();
    if(ans != 0)
        fout << "4 " << ans/3 << "\n";
    else if(ans = count3())
        fout << "3 " << ans/3 << "\n";
    else fout << "2 " << m << "\n";
    return 0;
}