/// 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 cnt4 = 0;
    int cnt3 = 0;
    int cnt2 = 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])
                        cnt4++;
                }
                if (M[i][j] && M[i][k] && M[j][k])
                    cnt3++;
            }
            if (M[i][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;
}