#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define mod 666013
class Hash{
    private:
        vector<pair<long,long> > C[mod];
        long getKey(long x,long y){return (x*1374+y)%mod;}

    public:
        Hash(){
            for(long i=0;i<mod;i++) C[i].clear();
        }
        void addKey(long x,long y){
            C[getKey(x,y)].push_back(make_pair(x,y));
        }
        void rmKey(long x,long y){
            pair<long,long> p = make_pair(x,y);
            long key = getKey(x,y);

            for(long i=0;i<C[key].size();i++){
                if(C[key][i]!=p) continue;
                C[key][i] = C[key][C[key].size()-1];
                C[key].pop_back();
                break;
            }
        }
        bool isKey(long x,long y){
            pair<long,long> p = make_pair(x,y);
            long key = getKey(p.first,p.second);
            for(long i=0;i<C[key].size();i++)
                if(C[key][i] == p) return true;
            return false;
        }
};

#define maxN 30011

long n,m,i,x,y,node,j;
vector<long> list[maxN];
long gr[maxN];
Hash H;

long ans[10];
queue<long> Q;

bool us[10],alrdn[maxN];
long tot;

bool Check(){
    vector<long> nodes; nodes.clear(); nodes.push_back(node);
    long i,j;

    for(i=0;i<list[node].size();i++){
        if(!us[i]) continue;
        nodes.push_back(list[node][i]);
    }

    for(i=0;i<nodes.size();i++){
        for(j=i+1;j<nodes.size();j++){
            if(!H.isKey(nodes[i],nodes[j])) return false;
        }
    }
    return true;
}

void Try(long pas){
    if(pas==list[node].size()){
        if(tot!=2 && tot!=3) return;
        if(Check()){
            if(tot==2) ans[3]++;
            else       ans[4]++;
        }

        return;
    }

    tot++; us[pas] = true; Try(pas+1);
    tot--; us[pas] = false; Try(pas+1);
}

int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);

    scanf("%ld %ld",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%ld %ld",&x,&y);
        gr[x]++; gr[y]++;
        list[x].push_back(y);
        list[y].push_back(x);
        H.addKey(x,y); H.addKey(y,x);
    }

    ans[1]=n; ans[2] = m;
    ans[3] = ans[4] = 0;

    for(i=1;i<=n;i++) if(list[i].size()<=5) {Q.push(i);alrdn[i]=true;}

    while(!Q.empty()){
        //! Incerc sa formez subgrafuri complete
        node = Q.front(); Q.pop();
        if(list[node].size()<2) continue;
        Try(0);

        //! Elimin nodul
        alrdn[node] = true;
        for(i=0;i<list[node].size();i++){
            long newNode = list[node][i];

            gr[newNode]--;
            for(j=0;j<list[newNode].size();j++){
                if(list[newNode][j]!=node) continue;
                list[newNode][j] = list[newNode][ list[newNode].size()-1 ];
                list[newNode].pop_back(); break;
            }

            H.rmKey(node,newNode);
            H.rmKey(newNode,node);
        }

        //! Adaug noduri noi in coada
        for(i=0;i<list[node].size();i++){
            long newNode = list[node][i];

            if(alrdn[newNode]) continue;
            if(list[newNode].size()<=5) Q.push(i);
            alrdn[newNode] = true;
        }
    }

    if(ans[4]) printf("%ld %ld",4,ans[4]); else
    if(ans[3]) printf("%ld %ld",3,ans[3]); else
               printf("%ld %ld",2,ans[2]);

    return 0;
}