#include <cstdio>
#include <bitset>
#include <vector>
#include <unordered_set>
#include <queue>
#define nmax 30005
using namespace std;
unordered_set <int> v[nmax];
unordered_set <int> :: iterator a,b,c;
queue <int> q;
bitset <nmax> u;
int n,m,clique3,clique4;




inline void countclique()
{
    int i,nod;
    for (i=1;i<=n;i++)
        if (v[i].size()<6)
            q.push(i),u[i]=1;

    while (!q.empty()) {
            nod=q.front();
            q.pop();
            for (a=v[nod].begin();a!=v[nod].end();a++)
                for (b=a,b++;b!=v[nod].end();b++) {

                    if (v[*b].count(*a)) {
                        clique3++;
                        for (c=b,c++;c!=v[nod].end();c++)
                            if (v[*c].count(*a)&&v[*c].count(*b))
                                clique4++;
                    }
                }

            for (a=v[nod].begin();a!=v[nod].end();a++) {
                v[*a].erase(nod);
                if (u[*a]==0&&v[*a].size()<6)
                    q.push(*a);
            }
            v[nod].clear();
    }
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    scanf("%d %d",&n,&m);
    int i,j,p,t;
    for (i=1;i<=m;i++) {
        scanf("%d %d",&p,&t);
        v[p].insert(t);
        v[t].insert(p);
    }
    countclique();
    if (clique4)
        printf("4 %d\n",clique4);
    else
        if (clique3)
            printf("3 %d\n",clique3);
            else
                printf("2 %d\n",m);
    return 0;
}