#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5 + 10;
long long n, m, mx, cnt, ans;
vector<long long> e[MAXN], adj[2][MAXN];
bool mark[MAXN], owner[MAXN];
void dfs(long long x, bool o) {
  adj[o][cnt].push_back(x);
  mark[x] = 1;
  owner[x] = o;
  for (long long i = 0; i < e[x].size(); i++) {
    if (mark[e[x][i]] == 1 && owner[e[x][i]] == owner[x]) {
      cout << "0 1";
      exit(0);
    }
    if (mark[e[x][i]] == 0) dfs(e[x][i], 1 - o);
  }
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m;
  if (!m) return cout << "3 " << n * (n - 1) * (n - 2) / 6, 0;
  for (long long i = 0; i < m; i++) {
    long long u, v;
    cin >> u >> v;
    e[v].push_back(u);
    e[u].push_back(v);
  }
  for (long long i = 1; i <= n; i++) {
    long long q = e[i].size();
    mx = max(mx, q);
  }
  if (mx == 1) {
    ans = (n - 2) * m;
    cout << "2 " << ans;
    return 0;
  }
  for (long long i = 1; i <= n; i++)
    if (!mark[i]) {
      dfs(i, 0);
      cnt++;
    }
  for (long long i = 0; i < cnt; i++) {
    long long x = adj[0][i].size(), y = adj[1][i].size();
    ans += x * (x - 1) / 2;
    ans += y * (y - 1) / 2;
  }
  cout << "1 " << ans;
}
