#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100, M = 5;
long long n, m, u, v, ans1, ans2, help, c[N], cnt[M];
vector<int> nei[N];
bool odd_cycle(int v) {
  cnt[c[v]]++;
  help += nei[v].size();
  for (int u : nei[v])
    if (c[u] == 0) {
      c[u] = c[v] ^ 3;
      if (odd_cycle(u)) return true;
    } else if (c[v] == c[u])
      return true;
  return false;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> m;
  if (m == 0) {
    cout << 3 << ' ' << n * (n - 1) * (n - 2) / 6;
    return 0;
  }
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    nei[--u].push_back(--v);
    nei[v].push_back(u);
  }
  for (int i = 0; i < n; i++)
    if (c[i] == 0) {
      help = cnt[1] = cnt[2] = 0;
      c[i] = 1;
      if (odd_cycle(i)) {
        cout << "0 1";
        return 0;
      }
      ans1 += (cnt[1] * (cnt[1] - 1) + cnt[2] * (cnt[2] - 1)) >> 1;
      ans2 += cnt[1] * cnt[2] * (cnt[1] + cnt[2] - 2) +
              help / 2 * (n - cnt[1] - cnt[2]);
    }
  if (ans1)
    cout << 1 << ' ' << ans1;
  else
    cout << 2 << ' ' << ans2 << '\n';
  return 0;
}
