#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > graph(100000);
bool visited[100000];
bool b1;
vector<int> odd;
vector<int> eve;
bool col[100000];
void dfs(int i) {
  if (!b1) {
    return;
  }
  for (int j = 0; j < graph[i].size(); j++) {
    if (visited[graph[i][j]]) {
      if (col[i] == col[graph[i][j]]) b1 = false;
    } else {
      visited[graph[i][j]] = true;
      if (col[i]) {
        col[graph[i][j]] = false;
        eve.push_back(graph[i][j]);
      } else {
        col[graph[i][j]] = true;
        odd.push_back(graph[i][j]);
      }
      dfs(graph[i][j]);
    }
  }
}
int main() {
  memset(visited, 0, sizeof visited);
  int n, m;
  scanf("%d %d", &n, &m);
  int a, b;
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    graph[b - 1].push_back(a - 1);
    graph[a - 1].push_back(b - 1);
  }
  long long ans1 = 3;
  long long ans2 = 0;
  long long singlets = 0;
  long long doublets = 0;
  for (int i = 0; i < n; i++) {
    if (!visited[i]) {
      b1 = true;
      eve.clear();
      odd.clear();
      col[i] = true;
      odd.push_back(i);
      visited[i] = true;
      dfs(i);
      if (!b1) {
        cout << 0 << " " << 1 << endl;
        return 0;
      }
      if (odd.size() == 1 && eve.size() == 0)
        singlets++;
      else if (eve.size() == 1 && odd.size() == 1) {
        if (ans1 > 2) ans1 = 2;
        doublets++;
      } else {
        if (ans1 > 1) ans1 = 1;
        ans2 += ((long long)(eve.size()) * (long long)(eve.size() - 1)) / 2 +
                ((long long)(odd.size()) * (long long)(odd.size() - 1)) / 2;
        ;
      }
    }
  }
  if (ans1 == 1) {
    cout << 1 << " " << ans2 << endl;
  } else if (ans1 == 2) {
    cout << 2 << " " << doublets * (2 * (doublets - 1) + singlets) << endl;
  } else
    cout << 3 << " " << singlets * (singlets - 1) * (singlets - 2) / 6 << endl;
  return 0;
}
