#include<bits/stdc++.h>
#define maxN 30005
using namespace std;
int gr[maxN],n,m,x,y,cnt[6];
vector<int> v[maxN];
typedef struct tip
{
    int x;
    bool operator<(const tip &other) const
    {
        return gr[x]>gr[other.x];
    }
};
set<tip> Set;

inline bool isEdge(int x,int y)
{
    if(y>v[x][gr[x]-1]) return 0;
    int pos=lower_bound(v[x].begin(),v[x].begin()+gr[x]-1,y)-v[x].begin();
    if(v[x][pos]==y) return 1;
    return 0;
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
    for(int i=1;i<=n;i++) gr[i]=v[i].size();
    for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
    for(int i=1;i<=n;i++)
        Set.insert({i});

    cnt[1]=n;
    cnt[2]=m;

    while(!Set.empty())
    {
        int nod=(*Set.begin()).x;
        Set.erase({nod});
        /**
            Cautam clica de 3
        **/
        for(int i=0;i<gr[nod];i++)
            for(int j=i+1;j<gr[nod];j++)
        {
            if(isEdge(v[nod][i],v[nod][j])) cnt[3]++;
        }

        /**
            Cautam clica de 4
        **/
        for(int i=0;i<gr[nod];i++)
            for(int j=i+1;j<gr[nod];j++)
                for(int k=j+1;k<gr[nod];k++)
        {
            if(isEdge(v[nod][i],v[nod][j]) && isEdge(v[nod][i],v[nod][k]) && isEdge(v[nod][j],v[nod][k])) cnt[4]++;
        }

        /**
            Stergem nodul
        **/
        for(int i=0;i<gr[nod];i++)
        {
            int vec=v[nod][i];
            int pos=lower_bound(v[vec].begin(),v[vec].begin()+gr[vec]-1,nod)-v[vec].begin();
            swap(v[vec][pos],v[vec][gr[vec]-1]);
            gr[vec]--;
        }
    }

    for(int i=4;i>=1;i--)
    {
        if(cnt[i])
        {
        printf("%d ",i);
        printf("%d\n",cnt[i]);
        break;
        }
    }

    return 0;
}