#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
long long N, M, u, v;
vector<vector<int> > G;
int c[maxn];
bool vis[maxn];
void color(int node) {
  vis[node] = true;
  for (int i = 0; i < G[node].size(); ++i) {
    if (!vis[G[node][i]]) {
      c[G[node][i]] = c[node] ^ 1;
      color(G[node][i]);
    }
  }
}
int W = 0, B;
int dfs(int node) {
  if (c[node] == 0) {
    W++;
  } else {
    B++;
  }
  vis[node] = true;
  for (int i = 0; i < G[node].size(); ++i) {
    if (!vis[G[node][i]]) {
      dfs(G[node][i]);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> M;
  G.resize(N + 1);
  for (int i = 0; i < M; ++i) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  for (int i = 1; i <= N; ++i) {
    if (!vis[i]) {
      c[i] = 0;
      color(i);
    }
  }
  bool is_bipartite = true;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < G[i].size(); ++j) {
      if (c[i] == c[G[i][j]]) {
        is_bipartite = false;
        break;
      }
    }
    if (!is_bipartite) {
      break;
    }
  }
  if (!is_bipartite) {
    cout << 0 << " " << 1 << "\n";
    return 0;
  }
  for (int i = 1; i <= N; ++i) {
    vis[i] = false;
  }
  int fans = 3;
  vector<long long> setA, setB;
  for (int i = 1; i <= N; ++i) {
    if (!vis[i]) {
      W = 0;
      B = 0;
      dfs(i);
      setA.push_back(W);
      setB.push_back(B);
    }
  }
  fans = 3;
  long long one = 0, two = 0;
  for (int i = 0; i < setA.size(); ++i) {
    if (setA[i] + setB[i] >= 1) {
      one++;
    }
    if (setA[i] + setB[i] >= 2) {
      two++;
    }
  }
  if (one >= 2 and two >= 1) {
    fans = 2;
  }
  for (int i = 0; i < setA.size(); ++i) {
    if (setA[i] > 1 or setB[i] > 1) {
      fans = 1;
    }
  }
  long long ways = 0;
  cout << fans << " ";
  if (fans == 3) {
    cout << (N * (N - 1) * (N - 2)) / 6;
    return 0;
  }
  if (fans == 2) {
    for (int i = 0; i < setA.size(); ++i) {
      if (setA[i] + setB[i] > 1) {
        one--;
      }
    }
    cout << (two * (N - 2));
    return 0;
  }
  for (int i = 0; i < setA.size(); ++i) {
    if (setA[i] >= 2) {
      ways += (setA[i] * (setA[i] - 1)) / 2;
    }
    if (setB[i] >= 2) {
      ways += (setB[i] * (setB[i] - 1)) / 2;
    }
  }
  cout << ways << "\n";
  return 0;
}
