// un graf planar poate avea subgrafuri complete de cel mult 4 noduri

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define pii pair <int, int>
#define fs first
#define sc second
#define Nmax 30005

using namespace std;

ifstream f("count.in");
ofstream g("count.out");

int n, m, k, ans;
set <int> s[Nmax];
vector <int> v[Nmax], r;
vector <pii> edge;
vector <int> ::iterator it1, it2;

int main()
{
    f >> n >> m;

    for (int i = 1, x, y; i <= m; i++)
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        s[x].insert(y);
        s[y].insert(x);
        edge.push_back({x, y});
    }

    for (auto i:edge)
    {
        int x=i.fs, y=i.sc;

        r.clear();
        for (auto j:v[x])
            if (s[y].find(j) != s[y].end()) r.push_back(j);

        for (it1 = r.begin(); it1 != r.end(); it1++)
            for (it2 = it1+1; it2 != r.end(); it2++)
                if(s[*it1].find(*it2) != s[*it1].end()) ans++;
    }

    if (ans!=0)
    {
        g << "4 " << ans/6 << '\n';
        return 0;
    }

    for (auto i:edge)
    {
        int x=i.fs, y=i.sc;

        for (auto j:v[x])
            if (s[y].find(j) != s[y].end()) ans++;
    }

    if (ans!=0) g << "3 " << ans/3 << '\n';
    else g << "2 " << m << '\n';

    return 0;
}