#include <bits/stdc++.h>
#pragma comment(linker, "/stack:102400000,102400000")
using namespace std;
int lowbit(int x) { return (x & -x); }
template <class T_>
T_ f_abs(T_ x) {
  return x < 0 ? -x : x;
}
template <class T_>
T_ f_max(T_ a, T_ b) {
  return a > b ? a : b;
}
template <class T_>
T_ f_min(T_ a, T_ b) {
  return a < b ? a : b;
}
template <class T_>
void chkmax(T_ &a, T_ b) {
  if (a == -1 || a < b) a = b;
}
template <class T_>
void chkmin(T_ &a, T_ b) {
  if (a == -1 || a > b) a = b;
}
template <class T_>
T_ gcd(T_ a, T_ b) {
  while (T_ t = a % b) a = b, b = t;
  return b;
}
template <class T_>
void f_swap(T_ &a, T_ &b) {
  T_ t = a;
  a = b;
  b = t;
}
const double eps = 1e-9;
const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1},
          dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const int inf = 0x7fffffff;
const int mod = 1000000007;
const int N = 100003;
int n, m, total, white[N], black[N], color[N];
vector<int> edg[N];
void Init() {
  for (int i = 0; i <= n; ++i) {
    color[i] = -1;
    white[i] = black[i] = 0;
    edg[i].clear();
  }
  total = 0;
}
void GetData() {
  int i, u, v;
  for (i = 0; i < m; ++i) {
    scanf("%d%d", &u, &v);
    edg[u].push_back(v);
    edg[v].push_back(u);
  }
}
bool Dfs(int u, int col) {
  if (color[u] != -1) return color[u] != col;
  color[u] = col;
  if (col == 1)
    white[total]++;
  else
    black[total]++;
  for (int i = 0; i < (int)edg[u].size(); ++i) {
    if (Dfs(edg[u][i], (col ^ 1))) return true;
  }
  return false;
}
void Solve() {
  int i, c1, c2;
  bool flag = false;
  long long ans = 0;
  if (m == 0)
    printf("3 %I64d\n", (long long)n * (n - 1) * (n - 2) / 6);
  else {
    for (i = 1; i <= n; ++i) {
      if (color[i] == -1) {
        if (Dfs(i, 1)) {
          flag = true;
          break;
        }
        total++;
      }
    }
    if (flag)
      printf("0 1\n");
    else {
      c1 = c2 = 0;
      for (i = 0; i < total; ++i) {
        if (white[i] + black[i] == 1)
          c1++;
        else if (white[i] + black[i] == 2)
          c2++;
        else
          break;
      }
      if (i == total) {
        ans = (long long)c2 * (n - 2);
        printf("2 %I64d\n", ans);
      } else {
        for (i = 0; i < total; ++i) {
          ans += (long long)white[i] * (white[i] - 1) / 2;
          ans += (long long)black[i] * (black[i] - 1) / 2;
        }
        printf("1 %I64d\n", ans);
      }
    }
  }
}
int main() {
  while (~scanf("%d%d", &n, &m)) {
    Init();
    GetData();
    Solve();
  }
  return 0;
}
