#include <bits/stdc++.h>
using namespace std;
const int N = 111111;
int size[3];
int colour[N];
bool ok = false;
bool used[N];
long long ans = 0;
vector<int> edge[N];
void dfs(int u) {
  used[u] = true;
  ans += size[colour[u]];
  size[colour[u]]++;
  for (int i = 0; i < edge[u].size(); i++) {
    int temp = edge[u][i];
    if (used[temp] == false) {
      colour[temp] = colour[u] ^ 1;
      dfs(temp);
    } else if (colour[temp] != (colour[u] ^ 1)) {
      ok = true;
    }
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  for (int i = 0; i < n; i++) {
    if (used[i] == false) {
      size[0] = size[1] = 0;
      dfs(i);
    }
  }
  if (ok == true) {
    cout << "0 1" << endl;
  } else if (ans == 0) {
    if (m == 0) {
      ans = (long long)n * (n - 1) * (n - 2);
      ans /= 6;
      cout << "3 " << ans << endl;
    } else {
      cout << "2 " << (long long)m * (n - 2) << endl;
    }
  } else {
    cout << "1 " << ans << endl;
  }
  return 0;
}
