#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long side[300001];
vector<long long> edges[300001];
bool vis[300001];
bool res = 1;
map<long long, long long> mp;
long long dfs(long long u, long long s) {
  vis[u] = 1;
  side[u] = s;
  ++mp[s];
  long long ret = 1;
  for (long long i = 0; i < edges[u].size(); ++i) {
    long long nxt = edges[u][i];
    if (vis[nxt] && side[u] == side[nxt]) {
      res = 0;
    } else if (!vis[nxt]) {
      ret += dfs(nxt, -s);
    }
  }
  return ret;
}
int32_t main() {
  cin >> n >> m;
  for (long long i = 0; i < m; ++i) {
    long long a, b;
    cin >> a >> b;
    edges[a].emplace_back(b);
    edges[b].emplace_back(a);
  }
  long long big = 0;
  long long cnt = 0;
  for (long long i = 1; i <= n; ++i) {
    if (vis[i]) continue;
    long long x = dfs(i, i);
    if (x == 2) ++cnt;
    big = max(big, x);
  }
  if (big == 1) {
    cout << "3 " << n * (n - 1) * (n - 2) / 6 << '\n';
  } else if (big == 2) {
    cout << "2 " << cnt * (n - 2) << '\n';
  } else if (res == 1) {
    long long ans = 0;
    for (auto it = mp.begin(); it != mp.end(); ++it) {
      long long x = (*it).second;
      ans += x * (x - 1) / 2;
    }
    cout << "1 " << ans << '\n';
  } else {
    cout << "0 1\n";
  }
  return 0;
}
