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

#define maxN 30001
#define Grad 6

using namespace std;

ifstream in;
ofstream out;

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

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].insert(y);
        g[y].insert(x);
    }
    in.close();

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

    for(int n1;!q.empty();q.pop())
    {
        n1=q.front();
        for(set <int>::iterator n2=g[n1].begin();n2!=g[n1].end();++n2)
        {
            if(n1>=*n2) continue;
            for(set <int>::iterator n3=g[*n2].begin();n3!=g[*n2].end();++n3)
            {
                if(*n2>=*n3) continue;
                if(g[n1].find(*n3)==g[n1].end()) continue;
                ++com3;
                for(set <int>::iterator n4=g[*n3].begin();n4!=g[*n3].end();++n4)
                {
                    if(*n3>=*n4) continue;
                    if(g[n1].find(*n4)==g[n1].end()) continue;
                    if(g[*n2].find(*n4)==g[*n2].end()) continue;
                    ++com4;
                }
            }
        }

        for(set <int>::iterator n2=g[n1].begin();n2!=g[n1].end();++n2)
        {
            g[*n2].erase(n1);
            if(!use[*n2]&&g[*n2].size()<Grad) {q.push(*n2); use[*n2]=1;}
        }
        g[n1].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;
}