/// infoarena.ro/problema/count
#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define po pop_back

#define NMax 2005

#define ll long long

using namespace std;

ifstream f("count.in");
ofstream g("count.out");

int n, m;
bitset<NMax> M[NMax];
int GR[NMax];
vector<int> noduri;

void read() {
    f>>n>>m;
    assert(n <= 2000);
    for (int i=1;i<=m;i++) {
        int x, y;
        f>>x>>y;
        GR[x]++;
        GR[y]++;
        M[x][y] = 1;
        M[y][x] = 1;
    }
}

void solve() {
    int cnt4 = 0;
    int cnt3 = 0;
    int cnt2 = 0;

    noduri.pb(0);
    for (int i=1;i<=n;i++)
        if (GR[i] < 6)
            noduri.pb(i);

    for (int i=1;i<noduri.size();i++)
        for (int j=i+1;j<noduri.size();j++) {
            for (int k=j+1;k<noduri.size();k++) {
                for (int p=k+1;p<noduri.size();p++) {
                    if (M[noduri[i]][noduri[j]] && M[noduri[j]][noduri[k]] && M[noduri[k]][noduri[p]] &&
                        M[noduri[i]][noduri[p]] && M[noduri[j]][noduri[p]] && M[noduri[i]][noduri[k]])
                        cnt4++;
                }
                if (M[noduri[i]][noduri[j]] && M[noduri[i]][noduri[k]] && M[noduri[j]][noduri[k]])
                    cnt3++;
            }
            if (M[noduri[i]][noduri[j]])
                cnt2++;
        }

    if (cnt4 > 0) {
        g<<4<<' '<<cnt4<<'\n';
        return;
    }
    if (cnt3 > 0) {
        g<<3<<' '<<cnt3<<'\n';
        return;
    }
    if (cnt2 > 0) {
        g<<2<<' '<<cnt2<<'\n';
    }

    g<<1<<' '<<n<<'\n';
}

int main() {

    read();
    solve();

    f.close(); g.close();
    return 0;
}