#include <bits/stdc++.h>
using namespace std;
int compcnt;
long long cnt0[100010];
long long cnt1[100010];
bool mark[100010];
long long cnttwo, cntone;
vector<int> v[100010];
int part[100010];
bool g;
void go(int cur, int f) {
  mark[cur] = 1;
  part[cur] = f;
  if (f == 0)
    cnt0[compcnt]++;
  else
    cnt1[compcnt]++;
  int i;
  for (i = 0; i < v[cur].size(); ++i) {
    if (!mark[v[cur][i]]) {
      go(v[cur][i], 1 - f);
      if (g) return;
    } else {
      if (part[v[cur][i]] != (1 - f)) {
        g = 1;
        return;
      }
    }
  }
}
int main() {
  g = 0;
  int i, n, m, x, y;
  long long maxx = -1;
  for (i = 0; i < 100010; ++i) cnt1[i] = cnt0[i] = 0;
  scanf("%d", &n);
  scanf("%d", &m);
  while (m--) {
    scanf("%d", &x);
    scanf("%d", &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }
  compcnt = 0;
  cnttwo = cntone = 0;
  for (i = 1; i <= n; ++i) mark[i] = 0;
  for (i = 0; i < n; ++i) {
    if (!mark[i]) {
      go(i, 0);
      if (g) break;
      maxx = max(maxx, cnt0[compcnt] + cnt1[compcnt]);
      if (cnt0[compcnt] + cnt1[compcnt] == 1)
        cntone++;
      else if (cnt0[compcnt] + cnt1[compcnt] == 2)
        cnttwo++;
      compcnt++;
    }
  }
  long long ans = 0;
  if (g)
    printf("%d %d", 0, 1);
  else if (maxx >= 3) {
    for (i = 0; i < compcnt; ++i) {
      ans = ans + cnt0[i] * (cnt0[i] - 1) / 2;
      ans = ans + cnt1[i] * (cnt1[i] - 1) / 2;
    }
    printf("%d %lld", 1, ans);
  } else if (maxx == 2) {
    ans = cnttwo * (n - 2);
    printf("%d %lld", 2, ans);
  } else {
    long long n1 = n;
    ans = n1 * (n1 - 1) * (n1 - 2) / 6;
    printf("%d %lld", 3, ans);
  }
}
