#include <bits/stdc++.h>
using namespace std;
int n, m, say[100005], bay, ts, cs, mark[100005];
long long int cev;
vector<int> yol[100005];
int dfs(int k, int tc) {
  mark[k] = tc;
  if (tc == 0)
    ts++;
  else
    cs++;
  for (int i = 0; i < (int)yol[k].size(); i++)
    if (mark[yol[k][i]] == -1) {
      dfs(yol[k][i], 1 - tc);
    } else if (mark[yol[k][i]] == tc) {
      printf("0 1");
      exit(0);
    }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int o1, o2;
    scanf("%d %d", &o1, &o2);
    yol[o1].push_back(o2);
    yol[o2].push_back(o1);
    say[o1]++;
    say[o2]++;
    if (say[o1] > 1) bay = 1;
  }
  if (m == 0) {
    printf("3 %lld", n * 1ll * (n - 1) * (n - 2) / 6);
    return 0;
  }
  if (bay == 0) {
    printf("2 %lld\n", m * 1ll * (n - 2));
    return 0;
  }
  memset(mark, -1, sizeof(mark));
  for (int i = 1; i <= n; i++)
    if (mark[i] == -1) {
      ts = 0, cs = 0;
      dfs(i, 0);
      cev += ts * 1ll * (ts - 1) / 2;
      cev += cs * 1ll * (cs - 1) / 2;
    }
  printf("1 %lld", cev);
}
