#include <bits/stdc++.h>

using namespace std;

ifstream fin ("count.in");
ofstream fout ("count.out");

const int Nmax = 30005;

bool erased[Nmax], used[Nmax];
int x, y, grad[Nmax], n, m, ans, cnt3, cnt4, i;
queue<int> q;
vector<int> v[Nmax];

bool edge(int x, int y)
{
    if(v[x].size() > v[y].size()) swap(x, y);
    int st = 0, dr = v[x].size() - 1, mid;

    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(v[x][mid] == y) return 1;
        if(v[x][mid] < y) st = mid + 1;
            else dr = mid - 1;
    }
    return 0;
}

void solve()
{
    vector<int> meh;
    int sz, i, j, k, node;

    while(!q.empty())
    {
        node = q.front();
        erased[node] = 1;
        q.pop();
        meh.clear();

        for(auto it : v[node])
            if(!erased[it]) meh.push_back(it);

        sz = meh.size();
        for(i=0; i<sz; ++i)
            for(j=i+1; j<sz; ++j)
                if(edge(meh[i], meh[j]))
                {
                    ++cnt3;
                    for(k=j+1; k<sz; ++k)
                        if(edge(meh[k], meh[i]) && edge(meh[k], meh[j]))
                            ++cnt4;
                }

        for(i=0; i<sz; ++i)
        {
            --grad[meh[i]];
            if(!used[meh[i]] && grad[meh[i]] < 6)
            {
                used[meh[i]] = 1;
                q.push(meh[i]);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(i=1; i<=m; ++i)
    {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        ++grad[x]; ++grad[y];
    }

    for(i=1; i<=n; ++i)
    {
        sort(v[i].begin(), v[i].end());
        if(v[i].size() < 6)
        {
            q.push(i);
            used[i] = 1;
        }
    }

    solve();

    if(cnt4) fout << 4 << ' ' << cnt4 << '\n';
        else if(cnt3) fout << 3 << ' ' << cnt3 << '\n';
            else cout << 2 << ' ' << m << '\n';

    return 0;
}