#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
bitset<MAXN> b;
vector<int> adj[MAXN];
int n, m, a1, a2, DELTA;
int c[MAXN];
long long ans = 0;
bool dfs(int v) {
  b[v] = true;
  for (auto i : adj[v]) {
    if (b[i] && c[i] == c[v]) return true;
    if (!b[i]) {
      c[i] = (c[v] % 2) + 1;
      if (!b[i] && dfs(i)) return true;
    }
  }
  return false;
}
bool check() {
  for (int i = 1; i <= n; ++i)
    if (!b[i]) {
      c[i] = 1;
      if (dfs(i)) return true;
    }
  return false;
}
pair<int, int> dfs_find(int v, int par) {
  b[v] = true;
  int ocnt = 0, ecnt = 0;
  for (auto i : adj[v])
    if (!b[i]) {
      pair<int, int> k = dfs_find(i, v);
      ocnt += k.first, ecnt += k.second;
    }
  ++ecnt;
  if (!par)
    ans += (long long)ocnt * (ocnt - 1) / 2 + (long long)ecnt * (ecnt - 1) / 2;
  return {ecnt, ocnt};
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> a1 >> a2;
    adj[a1].push_back(a2);
    adj[a2].push_back(a1);
    DELTA = max(DELTA, max((int)adj[a1].size(), (int)adj[a2].size()));
  }
  if (!m) return cout << "3 " << (long long)n * (n - 1) * (n - 2) / 6, 0;
  if (check()) return cout << "0 1", 0;
  if (DELTA < 2) return cout << "2 " << (long long)m * (n - 2), 0;
  for (int i = 0; i < MAXN; ++i) b[i] = false;
  for (int i = 1; i <= n; ++i)
    if (!b[i]) {
      b[i] = 1;
      dfs_find(i, 0);
    }
  cout << "1 " << ans << '\n';
  return 0;
}
