#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5;
vector<int> g[maxn];
int c[maxn];
int d[maxn];
long long x[2];
bool dfs(int v, int col) {
  x[col]++;
  c[v] = col;
  col ^= 1;
  for (int i = 0, sz = g[v].size(); i < sz; ++i) {
    int to = g[v][i];
    if (c[to] == c[v]) {
      return false;
    }
    if (c[to] == -1) {
      if (!dfs(to, col)) {
        return false;
      }
    }
  }
  return true;
}
long long cnk(long long s) { return s * (s - 1LL) / 2LL; }
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < n; ++i) c[i] = -1;
  bool bipartite = true;
  long long answer = 0;
  for (int i = 0; i < n; ++i) {
    if (c[i] == -1) {
      x[0] = x[1] = 0;
      bipartite &= dfs(i, 0);
      answer += cnk(x[0]) + cnk(x[1]);
    }
  }
  if (!bipartite) {
    cout << 0 << " " << 1;
    return 0;
  }
  if (m == 0) {
    long long ans = (n) * (n - 1LL) * (n - 2LL) / 6LL;
    cout << 3 << " " << ans;
    return 0;
  }
  for (int i = 0; i < n; ++i) d[i] = 0;
  for (int i = 0; i < n; ++i) ++d[g[i].size()];
  if (d[0] + d[1] == n) {
    cout << 2 << " ";
    cout << (n - 2LL) * d[1] / 2LL;
  } else {
    cout << 1 << " ";
    cout << answer;
  }
  return 0;
}
