#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:20000000")
using namespace std;
int ri() {
  int x;
  scanf("%d", &x);
  return x;
}
long long rll() {
  long long x;
  scanf("%lld", &x);
  return x;
}
vector<vector<int> > graph;
int clr[100500];
int clr2[100500];
int cnt1 = 0, cnt2 = 0;
bool dfs(int v, int parent = -1) {
  clr[v] = 1;
  bool res = false;
  for (int i = 0; i < graph[v].size(); i++) {
    int to = graph[v][i];
    if (to == parent) continue;
    if (clr[to] == 0) {
      if (dfs(to, v)) res = true;
    } else if (clr[to] == 1)
      res = true;
  }
  clr[v] = 2;
  return res;
}
void go(int v, int parent, int d) {
  clr2[v] = 1;
  if (d == 0)
    cnt1++;
  else
    cnt2++;
  for (int i = 0; i < graph[v].size(); i++) {
    int to = graph[v][i];
    if (to != parent) go(to, v, d ^ 1);
  }
}
void solve() {
  int n = ri(), m = ri();
  graph.resize(n + 1);
  bool yea = true;
  for (int i = (int)(1); i <= (int)(m); i++) {
    int a = ri(), b = ri();
    graph[a].push_back(b);
    graph[b].push_back(a);
    if (graph[a].size() > 1) yea = false;
    if (graph[b].size() > 1) yea = false;
  }
  long long res = 0;
  if (m == 0) {
    res = (long long)(n) * (long long)(n - 1) * (long long)(n - 2) / 6LL;
    cout << 3 << " " << res << endl;
    return;
  }
  if (yea) {
    int k = m;
    int ost = n - 2 * m;
    res = (long long)m * (long long)ost;
    res += (long long)m * (long long)(m - 1) * 2LL;
    cout << 2 << " " << res << endl;
    return;
  }
  bool wtf = false;
  for (int i = 1; i <= n; i++)
    if (clr[i] == 0) {
      if (dfs(i, -1)) {
        cnt1 = 1, cnt2 = 0;
        queue<int> st;
        st.push(i);
        clr2[i] = 1;
        while (!st.empty()) {
          for (int k = 0, tt = st.size(); k < tt; k++) {
            int v = st.front();
            st.pop();
            for (int j = 0; j < graph[v].size(); j++) {
              int to = graph[v][j];
              if (clr2[to] == 0) {
                clr2[to] = (clr2[v] == 1 ? 2 : 1);
                if (clr2[to] == 2)
                  cnt2++;
                else
                  cnt1++;
                st.push(to);
              } else if (clr2[to] == clr2[v]) {
                if (n == 2563) {
                  cout << to << " " << v << " " << clr2[to] << " " << clr2[v]
                       << endl;
                }
                cout << 0 << " " << 1 << endl;
                return;
              }
            }
          }
        }
        res += (long long)cnt1 * (long long)(cnt1 - 1) / 2LL;
        res += (long long)cnt2 * (long long)(cnt2 - 1) / 2LL;
      } else {
        cnt1 = 0, cnt2 = 0;
        go(i, -1, 0);
        res += (long long)cnt1 * (long long)(cnt1 - 1) / 2LL;
        res += (long long)cnt2 * (long long)(cnt2 - 1) / 2LL;
      }
    }
  cout << 1 << " " << res << endl;
}
int main() {
  solve();
  return 0;
}
