#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100;
vector<int> adj[MAXN];
int N, M;
int col[MAXN];
int cnt[2];
bool bipartite(int st) {
  col[st] = 1;
  queue<int> q;
  q.push(st);
  while (!q.empty()) {
    int cur = q.front();
    ++cnt[col[cur]];
    q.pop();
    for (int nxt : adj[cur]) {
      if (col[nxt] == -1) {
        col[nxt] = (col[cur] ^ 1);
        q.push(nxt);
      } else if (col[cur] == col[nxt]) {
        return false;
      }
    }
  }
  return true;
}
int main() {
  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  if (M == 0) {
    cout << 3 << ' ' << (long long)N * (N - 1) * (N - 2) / 6 << '\n';
    return 0;
  }
  int sz = -1;
  long long ways = 0;
  memset(col, -1, sizeof(col));
  for (int i = 0; i < N; ++i) {
    if (col[i] == -1) {
      cnt[0] = cnt[1] = 0;
      if (!bipartite(i)) {
        cout << "0 1\n";
        return 0;
      }
      sz = max(sz, cnt[0] + cnt[1]);
      ways += ((long long)cnt[0] * (cnt[0] - 1) / 2);
      ways += ((long long)cnt[1] * (cnt[1] - 1) / 2);
    }
  }
  if (sz > 2) {
    cout << "1 " << ways << '\n';
  } else {
    cout << "2 " << (long long)M * (N - 2) << '\n';
  }
  return 0;
}
