#include <fstream>
#include <string.h>
#include <vector>
#include <queue>

#define maxN 30001
#define MAX 6

using namespace std;

ifstream in;
ofstream out;

vector <int> g[maxN];
queue <int> q;
int use[maxN];

inline int edge(int x,int y)
{
    for(int i=0;i<g[x].size();++i)
        if(g[x][i]==y) return 1;
    return 0;
}

int main()
{
    int M,N,x,y;

    in.open("count.in");
    in>>N>>M;

    int com4=0;
    int com3=0;
    int com2=M;

    for(;M--;)
    {
        in>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    in.close();

    memset(use,0,sizeof(use));
    for(int i=1;i<=N;++i)
        if(g[i].size()<MAX) {q.push(i); use[i]=1;}

    for(int nod1,nod2,nod3,nod4;!q.empty();q.pop())
    {
        nod1=q.front();

        for(int i=0;i<g[nod1].size();++i)
        {
            nod2=g[nod1][i];
            if(nod1>nod2) continue;
            for(int j=0;j<g[nod2].size();++j)
            {
                nod3=g[nod2][j];
                if(nod2>nod3) continue;
                if(edge(nod1,nod3))
                {
                    ++com3;
                    for(int k=0;k<g[nod3].size();++k)
                    {
                        nod4=g[nod3][k];
                        if(nod3>nod4) continue;
                        if(edge(nod4,nod1)&&edge(nod2,nod4)) ++com4;
                    }
                }
            }
        }

        for(int i=0;i<g[nod1].size();++i)
        {
            nod2=g[nod1][i];
            for(int j=0;j<g[nod2].size();++j)
            {
                nod3=g[nod2][j];
                if(nod1==nod3)
                {
                    g[nod2][j]=g[nod2][g[nod2].size()-1];
                    g[nod2].pop_back();
                    if(g[nod2].size()<MAX&&!use[nod2]) {q.push(nod2); use[nod2]=1;}
                    break;
                }
            }
        }
        g[nod1].clear();
    }

    out.open("count.out");
    if(com4) out<<"4 "<<com4<<'\n';
    else
    if(com3) out<<"3 "<<com3<<'\n';
    else out<<"2 "<<com2<<'\n';
    out.close();

    return 0;
}