#include <bits/stdc++.h>
using namespace std;
const int MAX = 100005;
int n, m, flag;
vector<int> G[MAX];
int d[MAX];
int dep[MAX], sum1, sum2;
long long res;
void bfs(int x) {
  queue<int> que;
  dep[x] = 1;
  que.push(x);
  sum1 = 0;
  sum2 = 0;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    if (dep[u] % 2)
      sum1++;
    else
      sum2++;
    for (int i = 0; i < G[u].size(); ++i) {
      int v = G[u][i];
      if (dep[v] == dep[u]) {
        flag = 1;
        continue;
      }
      if (!dep[v]) {
        dep[v] = dep[u] + 1;
        que.push(v);
      }
    }
  }
}
int main() {
  int maxd = 0;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int t1, t2;
    scanf("%d%d", &t1, &t2);
    d[t1]++;
    d[t2]++;
    G[t1].push_back(t2);
    G[t2].push_back(t1);
    maxd = max(maxd, d[t1]);
    maxd = max(maxd, d[t2]);
  }
  if (maxd == 0) {
    printf("3 %I64d\n", (long long)n * (n - 1) * (n - 2) / 6);
    return 0;
  }
  if (maxd == 1) {
    printf("2 %I64d\n", (long long)m * (n - 2));
    return 0;
  }
  for (int i = 1; i <= n; ++i) {
    if (!dep[i]) {
      bfs(i);
      res += (long long)sum1 * (sum1 - 1) / 2;
      res += (long long)sum2 * (sum2 - 1) / 2;
    }
  }
  if (flag) {
    printf("0 1\n");
    return 0;
  }
  printf("1 %I64d\n", res);
  return 0;
}
