#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > component;
int island = 0;
int vis[100005];
vector<int> adj[100005];
int color[3];
bool zedge = 0;
bool oedge = 0;
bool tedge = 0;
void dfs(int u, int c) {
  color[c]++;
  vis[u] = c;
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (vis[v]) {
      if (vis[v] == vis[u]) zedge = 1;
      continue;
    }
    dfs(v, 3 - c);
  }
}
int main() {
  int N, M;
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i = 1; i <= N; i++) {
    if (vis[i]) continue;
    color[1] = 0;
    color[2] = 0;
    dfs(i, 1);
    if ((color[1] > 1 && color[2] > 0) || (color[1] > 0 && color[2] > 1))
      oedge = 1;
    if (color[1] > 0 && color[2] > 0) tedge = 1;
    if (color[1] + color[2] == 1) {
      island++;
      continue;
    }
    component.push_back(make_pair(color[1], color[2]));
  }
  long long ans1 = 0, ans2 = 0;
  if (zedge) {
    printf("0 1");
    return 0;
  }
  if (oedge) {
    ans1 = 1;
    for (int i = 0; i < component.size(); i++) {
      int b = component[i].first;
      int w = component[i].second;
      ans2 += (long long)b * (b - 1) / 2;
      ans2 += (long long)w * (w - 1) / 2;
    }
    printf("%lld %lld", ans1, ans2);
    return 0;
  }
  if (tedge) {
    ans1 = 2;
    for (int i = 0; i < component.size(); i++) {
      int b = component[i].first;
      int w = component[i].second;
      int diff = N - (b + w);
      ans2 += diff;
    }
    printf("%lld %lld", ans1, ans2);
    return 0;
  }
  ans1 = 3;
  ans2 = (long long)N * (N - 1) * (N - 2) / 6;
  printf("%lld %lld", ans1, ans2);
}
