#include <bits/stdc++.h>
using namespace std;
vector<int> E[100001];
int flag[100001], deg[100001], col[100001], cnt[2], a[100001], b[100001], n, cc;
bool dfs(int u) {
  for (int i = 0; i < E[u].size(); i++) {
    int v = E[u][i];
    if (col[v] != -1) {
      if (col[v] == col[u])
        return false;
      else
        continue;
    }
    col[v] = col[u] ^ 1;
    cnt[col[v]]++;
    if (!dfs(v)) return false;
  }
  return true;
}
bool solve() {
  memset(col, -1, sizeof(col));
  for (int i = 0; i < n; i++)
    if (col[i] == -1) {
      col[i] = 0;
      cnt[0] = 1, cnt[1] = 0;
      if (!dfs(i)) return true;
      a[cc] = cnt[0], b[cc++] = cnt[1];
    }
  return false;
}
int main() {
  int m, x, y;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 0; i <= n; i++) E[i].clear();
    memset(deg, 0, sizeof(deg));
    cc = 0;
    for (int i = 0; i < m; i++) {
      scanf("%d%d", &x, &y);
      x--, y--;
      E[x].push_back(y);
      E[y].push_back(x);
      deg[x]++, deg[y]++;
    }
    if (m == 0)
      printf("3 %I64d\n", (long long)n * (n - 1) * (n - 2) / 6);
    else {
      bool ok = 0;
      for (int i = 0; i < n && !ok; i++)
        if (deg[i] > 1) ok = 1;
      if (!ok) {
        printf("2 %I64d\n", (long long)m * (n - 2));
        break;
      }
      bool ret = solve();
      if (ret)
        printf("0 1\n");
      else {
        long long ans = 0;
        for (int i = 0; i < cc; i++) {
          ans += (long long)a[i] * (a[i] - 1) / 2;
          ans += (long long)b[i] * (b[i] - 1) / 2;
        }
        printf("1 %I64d\n", ans);
      }
    }
  }
}
