#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void amin(T &a, const T &b) {
  if (b < a) a = b;
}
template <class T>
inline void amax(T &a, const T &b) {
  if (a < b) a = b;
}
int N, M;
vector<vector<int> > G;
const int MAX = 100011;
int col[MAX], cc[MAX];
bool use[MAX];
bool dfs(int v) {
  for (__typeof((G[v]).begin()) e = (G[v]).begin(), e_end = (G[v]).end();
       e != e_end; ++e) {
    if (col[*e] == 0) {
      col[*e] = 3 - col[v];
      cc[*e] = cc[v];
      if (!dfs(*e)) return false;
    } else if (col[*e] != 3 - col[v]) {
      return false;
    }
  }
  return true;
}
bool two_coloring() {
  memset(cc, -1, sizeof cc);
  for (int i = 0, i_len = (N); i < i_len; ++i)
    if (col[i] == 0) {
      col[i] = 1;
      cc[i] = i;
      if (!dfs(i)) return false;
    }
  return true;
}
bool has_v() {
  for (int i = 0, i_len = (N); i < i_len; ++i)
    if (G[i].size() > 1u) return true;
  return false;
}
int tbl[2][MAX];
long long solve() {
  for (int i = 0, i_len = (N); i < i_len; ++i) {
    tbl[col[i] - 1][cc[i]]++;
  }
  long long ans = 0;
  for (int j = 0, j_len = (2); j < j_len; ++j)
    for (int i = 0, i_len = (N); i < i_len; ++i) {
      long long t = tbl[j][i];
      ans += t * (t - 1) / 2;
    }
  return ans;
}
int main() {
  scanf("%d%d", &N, &M);
  G.resize(N);
  for (int i = 0, i_len = (M); i < i_len; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  if (!two_coloring()) {
    puts("0 1");
  } else if (has_v()) {
    long long ans = solve();
    printf("1 %lld\n", ans);
  } else if (M) {
    printf("2 %lld\n", (long long)M * (N - 2));
  } else {
    printf("3 %lld\n", (long long)N * (N - 1) * (N - 2) / 6);
  }
  return 0;
}
