#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9, maxn = (int)1e5 + 1;
const double eps = (double)1e-8;
const int mod = (int)1000000007;
long long ans, kol, n, m, fl, x, y, c[100005], s[2];
vector<int> k;
vector<pair<int, int> > ss;
vector<int> a[100005];
void dzen(int v, int ch) {
  s[ch]++;
  kol++;
  c[v] = ch + 1;
  for (int i = (0); i <= ((int)a[v].size() - 1); i++) {
    if (c[a[v][i]] == ch + 1) fl = 1;
    if (c[a[v][i]] > 0) continue;
    dzen(a[v][i], !ch);
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  if (m == 0) {
    ans = (long long)n * (long long)(n - 1) * (long long)(n - 2);
    ans /= (long long)3;
    ans /= (long long)2;
    cout << "3 " << ans;
    return 0;
  }
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  fl = 1;
  for (int i = (1); i <= (n); i++) {
    if (a[i].size() >= 2) fl = 0;
  }
  if (fl) {
    ans = (long long)0;
    for (int i = (1); i <= (n); i++) {
      ans += (long long)a[i].size() * (long long)(n - 2);
    }
    ans /= (long long)2;
    cout << "2 " << ans;
    return 0;
  }
  memset((c), 0, sizeof(c));
  ;
  fl = 0;
  for (int i = (1); i <= (n); i++) {
    if (c[i]) continue;
    kol = 0;
    s[0] = 0;
    s[1] = 0;
    dzen(i, 0);
    k.push_back(kol);
    ss.push_back(make_pair((int)s[0], (int)s[1]));
  }
  if (fl) {
    cout << "0 1";
    return 0;
  }
  ans = 0;
  for (int i = (0); i <= ((int)k.size() - 1); i++) {
    ans +=
        ((long long)ss[i].first * (long long)(ss[i].first - 1)) / (long long)2;
    ans += ((long long)ss[i].second * (long long)(ss[i].second - 1)) /
           (long long)2;
  }
  cout << "1 " << ans;
  return 0;
}
