#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;
const int nmax=30005;
unordered_map<int,int> m[nmax];
vector<int> v[nmax];
set< pair<int,int> > s;
set< pair<int,int> >::iterator it;
int gr[nmax],del[nmax];
int nod[20];
int n,mu;
int i,x,y,nd,nr,j,k,trei,patru;
int chk_2(int x,int y)
{
    return (m[x][y]);
}
int chk_3(int x,int y,int z)
{
    return (m[x][y]&m[x][z]&m[y][z]);
}
int main()
{
    ifstream f("count.in");
    ofstream g("count.out");
    f>>n>>mu;
    for(i=1;i<=mu;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        m[x][y]=1;
        m[y][x]=1;
    }
    for(i=1;i<=n;i++)
    {
        gr[i]=v[i].size();
        s.insert({gr[i],i});
    }
     while(!s.empty())
    {
        it=s.begin();
        nr=0;
        x=(*it).second;
        s.erase(it);
        del[x]=1;
        for(i=0;i<v[x].size();i++)
           if(!del[v[x][i]])
        {
              nd=v[x][i];
              nod[++nr]=nd;
              s.erase({gr[nd],nd});
              gr[nd]--;
              s.insert({gr[nd],nd});
        }
        for(i=1;i<=nr;i++)
            for(j=i+1;j<=nr;j++)
        {
            trei+=chk_2(nod[i],nod[j]);
            for(k=j+1;k<=nr;k++)
                patru+=chk_3(nod[i],nod[j],nod[k]);
        }
    }
    if(trei)
    {
        if(patru)
        {
            g<<4<<' '<<patru;
        }
        else
        {
            g<<3<<' '<<trei;
        }
    }
    else g<<2<<' '<<m;

    return 0;
}