#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > v;
int visited[100005];
int dfs(int x, int comp) {
  visited[x] = comp;
  int sz = 1;
  for (int i = 0; i < v[x].size(); ++i) {
    if (visited[v[x][i]] == 0) {
      sz += dfs(v[x][i], comp);
    }
  }
  return sz;
}
pair<int, int> dfs2(int x, int color) {
  visited[x] = color;
  int next_color;
  if (color == 1) {
    next_color = 2;
  } else {
    next_color = 1;
  }
  int color_sz = 0;
  int next_color_sz = 0;
  if (color == 1) {
    color_sz++;
  } else {
    next_color_sz++;
  }
  bool ok = true;
  for (int i = 0; i < v[x].size(); ++i) {
    if (visited[v[x][i]] == color) {
      ok = false;
    } else if (visited[v[x][i]] == 0) {
      visited[v[x][i]] = next_color;
      pair<int, int> p = dfs2(v[x][i], next_color);
      if (p.first == -1) {
        ok = false;
      } else {
        color_sz += p.first;
        next_color_sz += p.second;
      }
    }
  }
  if (ok) {
    return make_pair(color_sz, next_color_sz);
  } else {
    return make_pair(-1, -1);
  }
}
int main() {
  long long n, m;
  cin >> n >> m;
  v.assign(n, vector<int>());
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  int comp = 0;
  int max_comp = 0;
  map<int, int> comp_start;
  map<int, int> comp_sz;
  for (int i = 0; i < n; ++i) {
    if (visited[i] == 0) {
      comp++;
      comp_start[comp] = i;
      int c_sz = dfs(i, comp);
      comp_sz[comp] = c_sz;
      max_comp = max(max_comp, c_sz);
    }
  }
  if (max_comp == 1) {
    cout << 3 << " " << (n * (n - 1) * (n - 2)) / 6 << endl;
  } else if (max_comp == 2) {
    cout << 2 << " " << (n - 2) * m << endl;
  } else {
    memset(visited, 0, sizeof(visited));
    long long res = 0;
    bool ok = true;
    for (int i = 1; i <= comp; ++i) {
      pair<int, int> p = dfs2(comp_start[i], 1);
      if (p.first == -1) ok = false;
      res += ((long long)p.first * (p.first - 1)) / 2 +
             ((long long)p.second * (p.second - 1)) / 2;
    }
    if (ok) {
      cout << 1 << " " << res << endl;
    } else {
      cout << "0 1" << endl;
    }
  }
  return 0;
}
