#include <bits/stdc++.h>
using namespace std;
const int INF = (-1u) / 2;
const long long int INF2 = (-1ull) / 2;
long long int a, b, i, d[1011000], j, k, n, m, timer = 0, l, r, x, y,
                                               us[100010];
long long int c[1011000], cnt = 0, fl = 0, a2, a3 = -1000000, ans = 0;
vector<long long int> g[100010];
void dfs(long long int v, long long int par) {
  fl++;
  c[d[v]]++;
  for (int i = 0; i < g[v].size(); i++) {
    int to = (g[v][i]);
    if (to == par) continue;
    if (d[to] == -1) {
      d[to] = d[v] ^ 1ll;
      dfs(to, v);
    } else {
      if (d[to] == d[v]) {
        cout << "0 1\n";
        exit(0);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (i = 0; i < n; i++) d[i] = -1;
  for (i = 0; i < m; i++) {
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if (m == 0) {
    cout << "3 " << (n * (n - 1) * (n - 2)) / 6ll << endl;
    return 0;
  }
  for (i = 0; i < n; i++) {
    if (d[i] == -1) {
      fl = 0;
      c[0] = c[1] = 0;
      d[i] = 0;
      dfs(i, -1);
      ans += ((c[0] * (c[0] - 1)) / 2ll + (c[1] * (c[1] - 1)) / 2ll);
      x = max(x, fl);
      if (fl <= 2) {
        if (fl == 2) {
          cnt += (n - 2);
        }
      }
    }
  }
  if (x <= 2) {
    cout << "2 " << cnt << endl;
  } else
    cout << "1 " << ans << endl;
  return 0;
}
