#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T sqr(const T& a) {
  return a * a;
}
template <typename T>
inline int sign(const T& a) {
  return a < 0 ? -1 : a > 0;
}
void task();
int main() {
  task();
  return 0;
}
int n, m;
vector<int> g[int(1e5) + 10];
vector<vector<int> > comp;
int color[int(1e5) + 10];
void go(int v) {
  for (int to : g[v]) {
    if (color[to] == color[v]) {
      printf("0 1");
      exit(0);
    }
    if (color[to] == 0) {
      color[to] = color[v] == 1 ? 2 : 1;
      comp.back().push_back(to);
      go(to);
    }
  }
}
void task() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if (m == 0) {
    printf("3 %I64d", n * (n - 1LL) * (n - 2LL) / 6);
    return;
  }
  for (int i = 0; i < n; ++i)
    if (color[i] == 0) {
      comp.push_back(vector<int>());
      comp.back().push_back(i);
      color[i] = 1;
      go(i);
    }
  int ok = 1;
  long long int ans = 0;
  for (auto& x : comp)
    if (x.size() > 2) {
      ok = 0;
      break;
    } else if (x.size() == 2) {
      ans += n - 2;
    }
  if (ok) {
    printf("2 %I64d", ans);
    return;
  }
  ans = 0;
  for (auto& v : comp) {
    int cnt1 = 0;
    for (int x : v) cnt1 += color[x] == 1;
    ans += cnt1 * (cnt1 - 1LL) / 2;
    cnt1 = v.size() - cnt1;
    ans += cnt1 * (cnt1 - 1LL) / 2;
  }
  printf("1 %I64d", ans);
}
