#include <bits/stdc++.h>
using namespace std;
const long long N = 100 * 1000 + 19;
const long long inf = 1e9 + 19;
const long long INF = 1e18 + 19;
long long n, m, color[N], cmp;
long long cnt1, cnt2;
vector<long long> adj[N], comp;
bool mark[N], flag = false;
long long ans = 0;
void dfs1(long long);
void dfs2(long long, long long);
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (long long i = 0; i < m; i++) {
    long long u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  if (m == 0) return cout << 3 << ' ' << 1ll * (n) * (n - 1) * (n - 2) / 6, 0;
  for (long long i = 0; i < n; i++)
    if (!mark[i]) {
      dfs1(i);
      comp.push_back(cmp);
      cmp = 0;
    }
  for (auto i : comp)
    if (i > 2) flag = true;
  if (!flag)
    return cout << 2 << ' ' << m * (n - 2), 0;
  else {
    memset(mark, 0, sizeof(mark));
    for (long long i = 0; i < n; i++) {
      cnt1 = cnt2 = 0;
      if (!mark[i]) {
        dfs2(i, 1);
        if (cnt1 + cnt2 > 1)
          ans +=
              1ll * ((cnt1 * (cnt1 - 1)) / 2) + 1ll * ((cnt2 * (cnt2 - 1)) / 2);
      }
    }
    cout << 1 << ' ' << ans;
  }
  return 0;
}
void dfs1(long long v) {
  cmp++;
  mark[v] = true;
  for (auto u : adj[v])
    if (!mark[u]) dfs1(u);
}
void dfs2(long long v, long long c) {
  mark[v] = true;
  color[v] = c;
  if (color[v] == 1) cnt1++;
  if (color[v] == 2) cnt2++;
  for (auto u : adj[v]) {
    if (!mark[u])
      dfs2(u, 3 - c);
    else if (color[u] == color[v]) {
      cout << 0 << ' ' << 1;
      exit(0);
    }
  }
}
