#include <bits/stdc++.h>
static constexpr int MAXN = 100000;
static std::vector<int> graph[MAXN];
static int cc_mark[MAXN];
static int cc_size[MAXN];
static bool color[MAXN];
static bool visited[MAXN];
static std::vector<int> last_used;
static bool make_luv(int node, bool prev) {
  if (visited[node]) return color[node] == !prev;
  last_used.push_back(node);
  color[node] = !prev;
  visited[node] = true;
  for (int adj : graph[node]) {
    if (!make_luv(adj, color[node])) {
      return false;
    }
  }
  return true;
}
static void dfs(int node, int mark) {
  if (visited[node]) return;
  cc_size[mark]++;
  cc_mark[node] = mark;
  visited[node] = true;
  for (int adj : graph[node]) {
    dfs(adj, mark);
  }
}
int main() {
  int nodes, edges;
  std::scanf("%d %d", &nodes, &edges);
  for (int i = 0; i < edges; i++) {
    int src, dest;
    std::scanf("%d %d", &src, &dest);
    src--, dest--;
    graph[src].push_back(dest);
    graph[dest].push_back(src);
  }
  int cc_count = 0;
  int shwetrakus[MAXN];
  for (int i = 0; i < nodes; i++) {
    if (!visited[i]) {
      shwetrakus[cc_count] = i;
      dfs(i, cc_count++);
    }
  }
  std::memset(visited, 0, sizeof(visited));
  int cnt[3] = {0};
  bool gu = false;
  std::vector<int> luvers;
  for (int i = 0; i < cc_count; i++) {
    if (cc_size[i] > 2) {
      gu = true;
      luvers.push_back(i);
    } else {
      cnt[cc_size[i]]++;
    }
  }
  if (gu) {
    long long answer = 0;
    for (int cc : luvers) {
      bool is_bipartite = true;
      if (!make_luv(shwetrakus[cc], false)) {
        for (int x : last_used) {
          color[x] = false;
          visited[x] = false;
        }
        last_used.clear();
        if (!make_luv(shwetrakus[cc], true)) {
          is_bipartite = false;
        }
      }
      if (!is_bipartite) {
        std::cout << "0 1\n";
        return EXIT_SUCCESS;
      }
      int set1 = 0, set2 = 0;
      for (int x : last_used) {
        set1 += color[x];
        set2 += !color[x];
        color[x] = false;
        visited[x] = false;
      }
      answer += 1LL * set1 * (set1 - 1) / 2;
      answer += 1LL * set2 * (set2 - 1) / 2;
      last_used.clear();
    }
    std::cout << "1 " << answer << std::endl;
  } else {
    if (cnt[2] != 0) {
      long long answer = 0;
      answer += 1LL * 2 * cnt[2] * (cnt[2] - 1);
      answer += 1LL * cnt[1] * cnt[2];
      std::cout << 2 << ' ' << answer << std::endl;
    } else {
      long long answer = 0;
      answer += 1LL * cnt[1] * (cnt[1] - 1) * (cnt[1] - 2) / 6;
      std::cout << 3 << ' ' << answer << std::endl;
    }
  }
  return EXIT_SUCCESS;
}
