#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
vector<int> pic[maxn];
int color[maxn];
int c1, c2;
bool check(int x) {
  for (int i = 0; i < pic[x].size(); i++) {
    int y = pic[x][i];
    if (color[x] == color[y]) return false;
    if (color[x] + color[y] == 3) continue;
    color[y] = 3 - color[x];
    if (!check(y)) return false;
  }
  return true;
}
void clear(int x) {
  if (color[x] == 1) c1++;
  if (color[x] == 2) c2++;
  color[x] = 0;
  for (int i = 0; i < pic[x].size(); i++) {
    int y = pic[x][i];
    if (color[y]) clear(y);
  }
}
long long solve(int n) {
  long long ret = 0;
  for (int i = 1; i <= n; i++)
    if (color[i]) {
      c1 = 0;
      c2 = 0;
      clear(i);
      ret += (long long)c1 * (long long)(c1 - 1) / 2;
      ret += (long long)c2 * (long long)(c2 - 1) / 2;
    }
  return ret;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  if (m == 0) {
    printf("3 ");
    long long ans = 1;
    for (int i = n; i >= n - 2; i--) ans *= (long long)i;
    ans /= 6;
    cout << ans << endl;
    return 0;
  }
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    pic[x].push_back(y);
    pic[y].push_back(x);
  }
  memset(color, 0, sizeof(color));
  for (int i = 1; i <= n; i++) {
    if (color[i] > 0) continue;
    color[i] = 1;
    if (!check(i)) {
      printf("0 1\n");
      return 0;
    }
  }
  for (int i = 1; i <= n; i++)
    if (pic[i].size() >= 2) {
      printf("1 ");
      long long ans = solve(n);
      cout << ans << endl;
      return 0;
    }
  printf("2 ");
  long long ans;
  ans = (long long)m * (long long)(n - 2);
  cout << ans << endl;
  return 0;
}
