#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define dbg(x) (cout<<#x<<" = "<<(x)<<endl)

using namespace std;
const int nmax = 30005;

int n,m,x,y,i,sol[5];

set<int> v[nmax];

queue<int> q;

int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(; m; m--)
    {
        scanf("%d%d",&x,&y);

        v[x].insert(y);
        v[y].insert(x);
    }

    for(i=1; i<=n; i++)
        if(v[i].size()<6)
            q.push(i);

    while(!q.empty())
    {
        x=q.front();
        q.pop();

        for(auto i:v[x])
            for(auto j:v[x])
                if(i!=j && v[i].find(j)!=v[i].end())
                    sol[3]++;

        for(auto i:v[x])
            for(auto j:v[x])
                for(auto k:v[x])
                    if(j!=i && k!=i && k!=j)
                        if(v[i].find(j)!=v[i].end() && v[i].find(k)!=v[i].end() && v[j].find(k)!=v[j].end())
                            sol[4]++;

        for(auto i:v[x])
        {
            v[i].erase(x);
            if(v[i].size()<6)
                q.push(i);
        }

        v[x].clear();
    }

    sol[1]=n;
    sol[2]=m;
    sol[3]/=2;
    sol[4]/=6;

    for(i=4; i>=1; i--)
        if(sol[i])
        {
            printf("%d %d\n",i,sol[i]);
            return 0;
        }

    return 0;
}