#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100005];
int vis[100005];
long long res, c[2];
void dfs2(int x, int par) {
  c[vis[x]]++;
  for (int i = 0; i < adj[x].size(); i++) {
    int y = adj[x][i];
    if (vis[y] == -1) vis[y] = vis[x] ^ 1, dfs2(y, x);
  }
  return;
}
void dfs(int x, int par) {
  for (int i = 0; i < adj[x].size(); i++) {
    int y = adj[x][i];
    if (y == par) continue;
    if (vis[y] == -1)
      vis[y] = vis[x] ^ 1, dfs(y, x);
    else if (vis[y] == vis[x])
      res++;
  }
  return;
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  while (m--) {
    int x, y;
    scanf("%d %d", &x, &y);
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  memset(vis, -1, sizeof vis);
  for (int i = 1; i <= n; i++)
    if (vis[i] == -1) vis[i] = 0, dfs(i, i);
  res /= 2;
  if (res) {
    printf("0 %lld\n", res);
    return 0;
  }
  memset(vis, -1, sizeof vis);
  for (int i = 1; i <= n; i++)
    if (vis[i] == -1) {
      c[0] = 0, c[1] = 0;
      vis[i] = 0, dfs2(i, i);
      res += (c[0] * (c[0] - 1)) / 2ll;
      res += (c[1] * (c[1] - 1)) / 2ll;
    }
  if (res) {
    printf("1 %lld\n", res);
    return 0;
  }
  long long x1 = 0, x0 = 0;
  for (int i = 1; i <= n; i++) {
    if (adj[i].empty())
      x0++;
    else
      x1++;
  }
  x1 /= 2;
  res = x1 * x0 + x1 * 2 * (x1 - 1);
  if (res) {
    printf("2 %lld\n", res);
    return 0;
  }
  res = n;
  res = (res * (res - 1) * (res - 2)) / 6ll;
  printf("3 %lld\n", res);
  return 0;
}
