#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 30003
#define MOD 389
#define DIM 10000
using namespace std;
char buff[DIM];
int poz=0;
void citeste(int &numar)
{
     numar = 0;
     while (buff[poz] < '0' || buff[poz] > '9')
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
}
int n,m;
struct str
{
    int in;
    int nod;
}ind[NMAX];
int mar,ct,ct2;
vector<int> h[NMAX][MOD],adj[NMAX];
bool rem[NMAX];
void addhash(int p1,int p2)
{
    h[p1][p2%MOD].push_back(p2);
}
int comp(const str &a,const str &b)
{
    return a.in<b.in;
}
int gas(int p1,int p2)
{
    int key=p2%MOD;
    vector<int>::iterator it;
    for(it=h[p1][key].begin();it!=h[p1][key].end();++it)
    {
        if(*it==p2) return 1;
    }
    return 0;
}
void gen3(int nod)
{
    int mar=adj[nod].size();
    for(int i=0;i<mar;i++)
    {
        if(rem[adj[nod][i]]==1) continue;
        for(int j=i+1;j<mar;j++)
        {
            if(rem[adj[nod][j]]==1) continue;
            if(gas(adj[nod][i],adj[nod][j])==1) ct++;
        }
    }
    rem[nod]=1;
}
void gen4(int nod)
{
    int mar=adj[nod].size();
    for(int i=0;i<mar;i++)
    {
        if(rem[adj[nod][i]]==1) continue;
        for(int j=i+1;j<mar;j++)
        {
            if(rem[adj[nod][j]]==1) continue;
            if(gas(adj[nod][i],adj[nod][j])==1)
            {
                for(int k=j+1;k<mar;k++)
                {
                    if(rem[adj[nod][k]]==1) continue;
                    if(gas(adj[nod][i],adj[nod][k])&&gas(adj[nod][j],adj[nod][k])) ct2++;
                }
            }
        }
    }
    rem[nod]=1;
}
int main()
{
    freopen ("count.in","r",stdin);
    freopen ("count.out","w",stdout);
    citeste(n),citeste(m);
    int x1,x2;
    for(int i=1;i<=n;i++) ind[i].nod=i;
    for(int i=1;i<=m;i++)
    {
        citeste(x1),citeste(x2);
        addhash(x1,x2);
        addhash(x2,x1);
        ind[x1].in++;
        ind[x2].in++;
        adj[x1].push_back(x2);
        adj[x2].push_back(x1);
    }
    sort(ind+1,ind+n+1,comp);
    for(int i=1;i<=n;i++) gen3(ind[i].nod);
    for(int i=1;i<=n;i++) rem[i]=0;
    for(int i=1;i<=n;i++) gen4(ind[i].nod);
    if(0==ct2) printf("3 %d\n",ct);
    else printf("%d %d\n",4,ct2);
}