#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const double eps = 0.0000000001;
const int N = 100000 + 100;
int head[N];
int tot;
struct node {
  int to, next;
} edge[N << 1];
int color[N];
int vis[N];
int a[N];
int b[N];
int num[N];
void init() {
  memset(head, -1, sizeof(head));
  tot = 0;
}
void add(int u, int v) {
  edge[tot].to = v;
  edge[tot].next = head[u];
  head[u] = tot++;
}
int DFS(int u, int t) {
  if (vis[u] == 0) {
    if (color[u] == 0) a[t]++;
    if (color[u] == 1) b[t]++;
    num[t]++;
  }
  vis[u] = 1;
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int v = edge[i].to;
    if (color[v] == 0) {
      color[v] = color[u] ^ 1;
      if (DFS(v, t) == 0) return 0;
    } else if (color[u] == color[v]) {
      return 0;
    }
  }
  return 1;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  init();
  int u, v;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  if (m == 0) {
    cout << 3 << " " << (long long)n * (n - 1) * (n - 2) / 6 << endl;
    return 0;
  }
  memset(color, 0, sizeof(color));
  memset(vis, 0, sizeof(vis));
  int flag = 0;
  int t = 0;
  for (int i = 1; i <= n; i++) {
    if (color[i] == 0 && vis[i] == 0) {
      if (DFS(i, ++t) == 0) {
        color[i] = 0;
        flag = 1;
        break;
      }
    }
  }
  if (flag == 1) {
    cout << 0 << " " << 1 << endl;
    return 0;
  }
  long long ans = 0;
  flag = 0;
  for (int i = 1; i <= t; i++) {
    if (num[i] <= 2) {
      flag++;
      continue;
    }
    ans = ans + (long long)a[i] * (a[i] - 1) / 2 +
          (long long)b[i] * (b[i] - 1) / 2;
  }
  if (flag != t)
    cout << 1 << " " << ans << endl;
  else {
    cout << 2 << " " << (long long)m * (n - 2) << endl;
  }
}
