#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:10240000000,10240000000")
struct edge {
  int v, next;
} e[500005 << 1];
int n, m, pre[500005], vis[500005], ecnt;
void init() {
  memset(pre, -1, sizeof(pre));
  memset(vis, 0, sizeof(vis));
  ecnt = 0;
}
void adde(int u, int v) {
  e[ecnt].v = v;
  e[ecnt].next = pre[u];
  pre[u] = ecnt++;
}
int c0;
int ct[3];
void dfs(int u, int type) {
  vis[u] = type;
  ct[type]++;
  for (int i = pre[u]; ~i; i = e[i].next) {
    int v = e[i].v;
    if (vis[v] == type) {
      c0 = 1;
      return;
    } else {
      if (!vis[v]) dfs(v, 3 - type);
    }
    if (c0) return;
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  init();
  if (!m) {
    printf("3 %I64d\n", (long long)n * (n - 1) * (n - 2) / 6);
    return 0;
  }
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    adde(u, v);
    adde(v, u);
  }
  c0 = 0;
  long long res = 0;
  long long cd = 0;
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      memset(ct, 0, sizeof(ct));
      dfs(i, 1);
      if (c0) break;
      int t = ct[1];
      res += (long long)t * (t - 1) / 2;
      t = ct[2];
      res += (long long)t * (t - 1) / 2;
      if (ct[1] >= 2) cd++;
    }
  long long k = m - cd * 2;
  if (c0)
    puts("0 1");
  else if (!res)
    printf("2 %I64d\n", cd * (cd - 1) / 2 * k * (k - 1) / 2 + cd + k * (n - 2));
  else
    printf("1 %I64d\n", res);
}
