#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int MAX_N = 100001;
const long long MOD = 1000000007;
const long long INF = 1e18;
long long n, m;
vector<int> adj[MAX_N];
int color[MAX_N], sz, num1, num2;
bool dfs(int curr) {
  if (color[curr] == 1)
    num1++;
  else
    num2++;
  for (int child : adj[curr]) {
    if (color[child]) {
      if (color[child] == color[curr]) return true;
      continue;
    }
    color[child] = 3 - color[curr];
    sz++;
    if (dfs(child)) return true;
  }
  return false;
}
int main(int argc, const char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  if (!m) {
    cout << 3 << ' ' << n * (n - 1ll) * (n - 2ll) / 6ll << endl;
    return 0;
  }
  for (int i = (0); i < (m); i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  long long a0 = 0, a1 = 0, a2 = 0, ans = 0;
  for (int i = (0); i < (n); i++)
    if (!color[i]) {
      color[i] = 1, sz = 0, num1 = 0, num2 = 0;
      if (dfs(i)) {
        cout << "0 1\n";
        return 0;
      }
      if (!sz)
        a0++;
      else if (sz == 1)
        a1++;
      else
        a2++;
      ans += num1 * (num1 - 1ll) / 2ll + num2 * (num2 - 1ll) / 2ll;
    }
  if (a2 == 0) {
    cout << "2 " << (n - 2ll) * a1 << endl;
    return 0;
  }
  cout << "1 " << ans << endl;
  return 0;
}
