/// 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;
int M[NMax][NMax];

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

void solve() {
    int cnt = 0;
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            for (int k=j+1;k<=n;k++)
                for (int p=k+1;p<=n;p++) {
                    if (M[i][j] && M[j][k] && M[k][p] && M[i][p] && M[j][p] && M[i][k])
                        cnt++;
                }

    if (cnt > 0) {
        g<<4<<' '<<cnt<<'\n';
        return;
    }

    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            for (int k=j+1;k<=n;k++) {
                if (M[i][j] && M[i][k] && M[j][k])
                    cnt++;
            }

    if (cnt > 0) {
        g<<3<<' '<<cnt<<'\n';
        return;
    }

    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            if (M[i][j])
                cnt++;

    if (cnt > 0) {
        g<<2<<' '<<cnt<<'\n';
        return;
    }

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

int main() {

    read();
    solve();

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