#include <bits/stdc++.h>
using namespace std;
vector<int> adj_list[100005];
long long int zero, one;
int visited[100005], color[100005];
int dfs(int n, int cur) {
  visited[n] = 1;
  vector<int>::iterator it;
  for (it = adj_list[n].begin(); it != adj_list[n].end(); it++) {
    if (visited[*it] == 0) {
      if (cur == 0)
        one++;
      else
        zero++;
      color[*it] = cur ^ 1;
      if (!dfs(*it, cur ^ 1)) {
        return 0;
      }
    } else if (color[*it] == cur)
      return 0;
  }
  return 1;
}
int main() {
  long long int n;
  int m, a, b, ans_is_one = 0;
  long long int ans = 0;
  memset(visited, 0, sizeof(visited));
  cin >> n >> m;
  if (m == 0) {
    cout << "3 " << (n * (n - 1) * (n - 2)) / 6 << '\n';
    return 0;
  }
  for (int i = 0; i < (m); ++i) {
    cin >> a >> b;
    if (visited[a] or visited[b]) ans_is_one = 1;
    adj_list[a].push_back(b);
    adj_list[b].push_back(a);
    visited[a] = visited[b] = 1;
  }
  if (!ans_is_one) {
    cout << "2 " << m * (n - 2) << '\n';
    return 0;
  }
  memset(visited, 0, sizeof(visited));
  for (int i = 0; i < (n + 1); ++i) color[i] = -1;
  int i = 1;
  while (i < n) {
    zero = 1;
    one = 0;
    if (!dfs(i, 0)) {
      cout << "0 1\n";
      return 0;
    }
    ans += (zero * (zero - 1)) / 2 + (one * (one - 1)) / 2;
    while (i < n and visited[i] == 1) i++;
  }
  cout << "1 " << ans << '\n';
  return 0;
}
