//#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <list>
#include <queue>
#include <bitset>

using namespace std;

list<int> graf[30005];
int deg[30005];
bitset<30005> viz;

#define pb push_back
#define mp make_pair

#define mod 6660011

list<pair<int,int> > h[mod];

inline void add(int x,int y)
{
    if(x>y)
        swap(x,y);

    int b=((19001*x)%mod+y)%mod;
    h[b].pb(mp(x,y));
}

bool ex(int x,int y)
{
    if(x>y)
        swap(x,y);
    int b=((19001*x)%mod+y)%mod;

    list<pair<int,int> >::iterator it;
    for(it=h[b].begin();it!=h[b].end();it++)
        if(it->first==x && it->second==y)
            break;

    if(it==h[b].end())
        return 0;
    return 1;
}

priority_queue<pair<int,int> > coada;

int main()
{
    ifstream cin("count.in");
    ofstream cout("count.out");

    int n=0,m=0,i,a,b;
    cin>>n>>m;

    for(i=0;i<m;i++)
    {
        cin>>a>>b;

        deg[a]++;
        deg[b]++;
        graf[a].pb(b);
        graf[b].pb(a);
        add(a,b);
    }

    for(i=1;i<=n;i++)
    {
        coada.push(mp(-deg[i],i));
        viz[i]=0;
    }
    int rasp=2;
    long long int cate=m;

    pair<int,int> y;

    vector<int> curent;

    list<int>::iterator it;
    vector<int>::iterator it2,it3,it4;

    while(!coada.empty())
    {
        y=coada.top();
        coada.pop();
        if(viz[y.second])
            continue;
        viz[y.second]=1;

        curent.clear();
        for(it=graf[y.second].begin();it!=graf[y.second].end();it++)
            if(!viz[*it])
            {
                deg[*it]--;
                coada.push(mp(-deg[*it],*it));
                curent.pb(*it);
            }

        for(it2=curent.begin();it2!=curent.end();it2++)
            for(it3=it2+1;it3!=curent.end();it3++)
                for(it4=it3+1;it4!=curent.end();it4++)
                {
                    if(ex(*it2,*it3) && ex(*it3,*it4) && ex(*it2,*it4))
                    {
                        if(rasp<4)
                        {
                            rasp=4;
                            cate=1;
                        }
                        else if(rasp==4)
                            cate++;
                    }
                }

        if(rasp<4)
            for(it2=curent.begin();it2!=curent.end();it2++)
                for(it3=it2+1;it3!=curent.end();it3++)
                    if(ex(*it2,*it3))
                    {
                        if(rasp<3)
                        {
                            rasp=3;
                            cate=1;
                        }
                        else if(rasp==3)
                            cate++;
                    }
    }
    cout<<rasp<<' '<<cate<<'\n';

    cin.close();
    cout.close();
    return 0;
}