#include <bits/stdc++.h>
using namespace std;
bool hasCycle = false;
bool bigComp = false;
bool bipartit = true;
long long nrplus, nrminus;
vector<int> v[100005];
int viz[100005];
int nrElem = 0;
void dfs(int node, int mark) {
  viz[node] = mark;
  ++nrElem;
  if (mark == 1)
    ++nrplus;
  else
    ++nrminus;
  for (int i = 0; i < v[node].size(); ++i) {
    if (viz[v[node][i]] == 0) {
      dfs(v[node][i], mark * -1);
    } else {
      if (viz[v[node][i]] != (mark * -1)) bipartit = false;
    }
  }
}
int main() {
  long long n, m, x, y;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> x >> y;
    v[x - 1].push_back(y - 1);
    v[y - 1].push_back(x - 1);
  }
  int nrConex = 0;
  long long sol = 0;
  for (int i = 0; i < n; ++i)
    if (viz[i] == 0) {
      nrplus = 0;
      nrminus = 0;
      nrElem = 0;
      dfs(i, 1);
      if (nrElem > 2) bigComp = true;
      sol += (nrplus - 1) * nrplus / 2;
      sol += (nrminus - 1) * nrminus / 2;
      ++nrConex;
    }
  if (nrConex == n) {
    cout << 3 << " " << n * (n - 1) * (n - 2) / 6;
    return 0;
  }
  if (bigComp == false) {
    cout << 2 << " " << (n - 2) * m;
    return 0;
  }
  if (bipartit == false) {
    cout << 0 << " " << 1;
    return 0;
  }
  cout << 1 << " " << sol;
}
