#include <bits/stdc++.h>
using namespace std;
bool cycle;
vector<vector<int>> V;
vector<vector<vector<int>>> P;
vector<int> color;
vector<bool> vis;
void dfs(int s, int col, int id) {
  vis[s] = true;
  color[s] = col;
  P[id][col].push_back(s);
  bool ret;
  for (int i = 0; i < V[s].size(); ++i) {
    int &u = V[s][i];
    if (!vis[u])
      dfs(u, !col, id);
    else if (color[u] == col)
      cycle = true;
  }
}
int main() {
  int N, M;
  while (cin >> N >> M) {
    V.clear();
    V.resize(N);
    for (int i = 0; i < M; ++i) {
      int a, b;
      cin >> a >> b;
      a--, b--;
      V[a].push_back(b);
      V[b].push_back(a);
    }
    vis.assign(N, 0);
    color.assign(N, -1);
    P.clear();
    int c = 0, maxS = 1;
    cycle = false;
    for (int i = 0; i < N && !cycle; ++i) {
      if (!vis[i]) {
        P.push_back(vector<vector<int>>(2));
        dfs(i, 0, c);
        maxS = max(maxS, (int)(P[c][0].size() + P[c][1].size()));
        c++;
      }
    }
    long long ans = 0;
    if (cycle) {
      cout << "0 1\n";
    } else if (maxS > 2) {
      for (int i = 0; i < P.size(); ++i) {
        long long a = P[i][0].size(), b = P[i][1].size();
        if (a > 1) ans += a * (a - 1) / 2;
        if (b > 1) ans += b * (b - 1) / 2;
      }
      cout << "1 " << ans << "\n";
    } else if (maxS == 2) {
      cout << "2 " << M * 1LL * (N - 2) << "\n";
    } else {
      for (long long i = 0, step = 1, prv = 0; i < N - 2; ++i) {
        ans += step + prv;
        prv = step + prv;
        step++;
      }
      cout << "3 " << ans << "\n";
    }
  }
  return 0;
}
