#include <bits/stdc++.h>
using namespace std;
bool bip = true;
long long ans = 0;
const int MAXN = 1e5 + 5;
int col[MAXN], sz[2];
vector<int> adj[MAXN];
void dfs(int v, int c) {
  col[v] = c;
  ans += sz[c];
  sz[c]++;
  for (int i = 0; i < (int)adj[v].size(); i++) {
    int u = adj[v][i];
    if (col[u] == -1)
      dfs(u, c ^ 1);
    else if (col[u] == col[v])
      bip = false;
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  memset(col, -1, sizeof col);
  for (int i = 1; i <= n; i++)
    if (col[i] == -1) {
      sz[0] = sz[1] = 0;
      dfs(i, 0);
    }
  if (!bip)
    cout << "0 1" << endl;
  else if (ans != 0)
    cout << "1 " << ans << endl;
  else {
    if (m == 0) {
      ans = (long long)n * (long long)(n - 1) * (long long)(n - 2);
      ans /= 6ll;
      cout << "3 " << ans << endl;
    } else {
      ans = (long long)m * (n - 2);
      cout << "2 " << ans << endl;
    }
  }
  return 0;
}
