#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000 * 1000 * 1000 + 7;
const long long INF = 2000ll * 1000 * 1000 * 1000 * 1000 * 1000;
const int MAXN = 100000 + 2;
const int MLOG = 22;
const int NMAX = 11;
vector<int> adj[MAXN];
int dg[MAXN], mark[MAXN];
long long cnt[2];
void dfs(int v, int c = 2) {
  mark[v] = c;
  cnt[c % 2]++;
  for (int nxt : adj[v]) {
    if (mark[nxt]) {
      if ((mark[nxt] & 1) == (c & 1)) {
        cout << "0 1";
        exit(0);
      }
    } else
      dfs(nxt, c + 1);
  }
}
int main() {
  ios_base ::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[--u].push_back(--v);
    adj[v].push_back(u);
    dg[v]++, dg[u]++;
  }
  if (!m) {
    cout << "3 " << (long long)n * (n - 1) * (n - 2) / 6;
    return 0;
  }
  if (*max_element(dg, dg + n) == 1) {
    cout << "2 " << (long long)m * (n - 2);
    return 0;
  }
  long long ans = 0;
  for (int i = 0; i < n; i++)
    if (!mark[i]) {
      cnt[0] = 0;
      cnt[1] = 0;
      dfs(i);
      cnt[0] *= cnt[0] - 1;
      cnt[1] *= cnt[1] - 1;
      ans += (cnt[1] + cnt[0]) / 2;
    }
  cout << "1 " << ans;
}
