#include <bits/stdc++.h>
using namespace std;
struct qxx {
  int to, nx;
} qx[200000];
int hd[100000], lq, a1[100000];
bool b1[100000], b2[100000];
void add(int a, int b) {
  qx[lq].to = b;
  qx[lq].nx = hd[a];
  hd[a] = lq++;
}
bool dfs(int a, int b, bool bl) {
  if (b1[a]) return b2[a] != bl;
  b1[a] = 1;
  b2[a] = bl;
  ++a1[bl];
  for (int i = hd[a]; ~i; i = qx[i].nx)
    if (qx[i].to != b)
      if (dfs(qx[i].to, a, !bl)) return 1;
  return 0;
}
int main() {
  memset(hd, -1, sizeof(hd));
  int n, m, a, b;
  bool bl = 1;
  long long o = 0;
  scanf("%d%d", &n, &m);
  if (!m) {
    printf("3 %I64d\n", (long long)n * (n - 1) * (n - 2) / 6);
    return 0;
  }
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &a, &b);
    --a, --b;
    if (a1[a] || a1[b]) bl = 0;
    add(a, b);
    add(b, a);
    ++a1[a];
    ++a1[b];
  }
  if (bl) {
    printf("2 %I64d\n", (long long)m * (n - 2));
    return 0;
  }
  for (int i = 0; i < n; ++i)
    if (!b1[i]) {
      a1[0] = a1[1] = 0;
      if (dfs(i, -1, 0)) {
        puts("0 1");
        return 0;
      }
      o +=
          ((long long)a1[0] * (a1[0] - 1) + (long long)a1[1] * (a1[1] - 1)) / 2;
    }
  printf("1 %I64d\n", o);
}
