#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 2;
int zero = 0, n, m, color[NMAX], viz[NMAX], cnt[2];
vector<int> gf[NMAX];
void dfs(int node) {
  cnt[color[node]]++;
  if (zero) return;
  viz[node] = 1;
  for (int i = 0; i < gf[node].size(); ++i) {
    int vc = gf[node][i];
    if (viz[vc] == 0) {
      color[vc] = 1 ^ color[node];
      dfs(vc);
    } else {
      if (color[vc] == color[node]) {
        zero = 1;
        return;
      }
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    gf[x].push_back(y);
    gf[y].push_back(x);
  }
  if (m == 0) {
    cout << "3 " << 1LL * n * (n - 1) * (n - 2) / 6 << "\n";
    return 0;
  }
  bool ok = true;
  for (int i = 1; i <= n; ++i) {
    if (gf[i].size() >= 2) {
      ok = false;
    }
  }
  if (ok) {
    cout << 2 << " " << 1LL * m * (n - 2) << "\n";
    return 0;
  }
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (viz[i] == 0) {
      for (int j = 0; j < 2; ++j) cnt[j] = 0;
      dfs(i);
      for (int j = 0; j < 2; ++j) {
        ans += 1LL * cnt[j] * (cnt[j] - 1) / 2;
      }
    }
  }
  if (zero) {
    cout << "0 1\n";
    return 0;
  }
  cout << 1 << " " << ans << "\n";
  return 0;
}
