#include <bits/stdc++.h>
#define DIM 30010
using namespace std;
ifstream fin("count.in");
ofstream fout("count.out");
int n,m,i,j,a,b,k,nod,f[5],v[10],x[10],g[DIM];
bitset<DIM> iq;
deque<int> q;
set<int> L[DIM];
void bt(int pas) {
    if (pas>k) {
        int nr=0;
        for (int i=1;i<=k;i++)
            if (x[i]==1)
                nr++;
        int ok=1;
        for (int i=1;i<=k;i++) {
            for (int j=i+1;j<=k;j++) {
                if (x[i]&x[j]) {
                    if (L[v[i]].find(v[j])==L[v[i]].end()) {
                        ok=0;
                        break;
                    }
                }
            }
        }
        if (ok)
            f[nr]++;
    }
    else {
        for (int i=0;i<=1;i++) {
            x[pas]=i;
            bt(pas+1);
        }
    }
}
int main() {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>a>>b;
        L[a].insert(b);
        L[b].insert(a);
        g[a]++, g[b]++;
    }
    for (i=1;i<=n;i++) {
        if (g[i]<6) {
            q.push_back(i);
            iq[i]=1;
        }
    }
    while (!q.empty()) {
        nod=q.front();
        q.pop_front();
        k=0;
        v[++k]=nod;
        for (auto it:L[nod])
            v[++k]=it;
        bt(1);
        for (auto it:L[nod]) {
            L[it].erase(nod);
            g[it]--;
            if (g[it]<6&&iq[it]==0) {
                q.push_back(it);
                iq[it]=1;
            }
        }
    }
    for (i=4;i>=1;i--) {
        if (f[i]) {
            fout<<i<<" "<<f[i];
            return 0;
        }
    }
    return 0;
}