#include <bits/stdc++.h>
using namespace std;
long long n, m;
vector<int> v[100010];
int visitado[100010];
long long par, impar;
void dfs(int vertice, int paridad) {
  if (visitado[vertice] != 0) {
    if (visitado[vertice] == -paridad) {
      cout << "0 1" << endl;
      exit(0);
    }
    return;
  }
  visitado[vertice] = paridad;
  if (paridad == 1)
    par++;
  else
    impar++;
  for (int i = 0; i < v[vertice].size(); i++) dfs(v[vertice][i], -paridad);
}
int main() {
  cin >> n >> m;
  int a, b;
  if (m == 0) {
    long long sol = n;
    sol = sol * (sol - 1) * (sol - 2) / 6;
    printf("3 %I64d\n", sol);
    return 0;
  }
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    a--;
    b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for (int i = 0; i < n; i++) visitado[i] = 0;
  long long sol = 0;
  for (int i = 0; i < n; i++)
    if (visitado[i] == 0) {
      par = 0;
      impar = 0;
      dfs(i, 1);
      sol += par * (par - 1) / 2;
      sol += impar * (impar - 1) / 2;
    }
  if (sol > 0)
    printf("1 %I64d\n", sol);
  else
    printf("2 %I64d\n", m * (n - 2));
}
