#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
struct Edge {
  int v, nxt;
  Edge() {}
  Edge(int v, int nxt) : v(v), nxt(nxt) {}
} es[N << 1];
int cnt;
int head[N];
void inline add_edge(int u, int v) {
  es[cnt] = Edge(v, head[u]);
  head[u] = cnt++;
  es[cnt] = Edge(u, head[v]);
  head[v] = cnt++;
}
bool vis[N];
long long c1, c0;
long long vcnt;
long long tmpc1, tmpc2;
bool col[N];
bool flag0, flag1;
void dfs(int u) {
  for (int i = head[u]; ~i; i = es[i].nxt) {
    int v = es[i].v;
    if (vis[v] == 0) {
      vis[v] = 1;
      vcnt++;
      col[v] = !col[u];
      if (col[v] == 1)
        c1++;
      else
        c0++;
      dfs(v);
    } else {
      if (flag0 == 0) flag0 = (col[u] == col[v]);
    }
  }
}
int main() {
  long long n, m;
  cin >> n >> m;
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= int(m); i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add_edge(u, v);
  }
  long long ans1 = 0, ans2 = 0;
  for (int i = n; i >= 1 && flag0 == 0; i--)
    if (!vis[i]) {
      vcnt = c1 = c0 = 0;
      vis[i] = 1;
      col[i] = 1;
      c1++;
      vcnt++;
      dfs(i);
      if (vcnt > 2) flag1 = 1;
      if (flag1) ans1 += c1 * (c1 - 1) / 2 + c0 * (c0 - 1) / 2;
      if (flag1 == 0) {
        if (vcnt == 2) tmpc2++;
        if (vcnt == 1) tmpc1++;
      }
    }
  if (flag0)
    puts("0 1");
  else if (flag1)
    printf("1 %I64d\n", ans1);
  else if (m == 0)
    printf("3 %I64d\n", n * (n - 1) * (n - 2) / 6);
  else {
    ans2 += tmpc1 * tmpc2;
    ans2 += tmpc2 * 2 * (tmpc2 - 1);
    printf("2 %I64d\n", ans2);
  }
}
