#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int> graph[MAXN];
bool visited[MAXN];
int color[MAXN];
struct component {
  bool isBipartite;
  long long int left, right;
  long long int v;
};
component DFS(int start, int c) {
  visited[start] = true;
  color[start] = c;
  component temp;
  temp.left = temp.right = temp.v = 0;
  temp.isBipartite = true;
  int nextColor;
  if (c == 1)
    nextColor = 2;
  else
    nextColor = 1;
  for (int i = 0; i < graph[start].size(); i++) {
    if (!visited[graph[start][i]]) {
      component temp1 = DFS(graph[start][i], nextColor);
      temp.left = temp.left + temp1.left;
      temp.right = temp.right + temp1.right;
      temp.v = temp.v + temp1.v;
      if (temp.isBipartite) temp.isBipartite = temp1.isBipartite;
    } else {
      if (color[graph[start][i]] != nextColor) temp.isBipartite = false;
    }
  }
  if (c == 1)
    temp.left++;
  else
    temp.right++;
  temp.v++;
  return temp;
}
int main() {
  ios::sync_with_stdio(false);
  long long int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
  vector<component> v2, v3;
  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;
    component temp;
    temp = DFS(i, 1);
    if (temp.v == 2)
      v2.push_back(temp);
    else {
      if (temp.v >= 3) {
        v3.push_back(temp);
        if (!temp.isBipartite) {
          cout << 0 << " " << 1 << endl;
          return 0;
        }
      }
    }
  }
  long long int ans = 0;
  if (v3.size() > 0) {
    for (int i = 0; i < v3.size(); i++) {
      if (v3[i].left >= 2)
        ans = (long long int)(ans + (v3[i].left * (v3[i].left - 1)) / 2);
      if (v3[i].right >= 2)
        ans = (long long int)(ans + (v3[i].right * (v3[i].right - 1)) / 2);
    }
    cout << 1 << " " << ans;
  } else {
    if (v2.size() > 0) {
      ans = (long long int)(m * (n - 2));
      cout << 2 << " " << ans;
    } else {
      ans = (long long int)((n * (n - 1) * (n - 2)) / 6);
      cout << 3 << " " << ans << endl;
    }
  }
  return 0;
}
