#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:667772160")
template <class T1>
void deb(T1 e1) {
  cout << e1 << endl;
}
template <class T1, class T2>
void deb(T1 e1, T2 e2) {
  cout << e1 << " " << e2 << endl;
}
template <class T1, class T2, class T3>
void deb(T1 e1, T2 e2, T3 e3) {
  cout << e1 << " " << e2 << " " << e3 << endl;
}
template <class T1, class T2, class T3, class T4>
void deb(T1 e1, T2 e2, T3 e3, T4 e4) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << endl;
}
template <class T1, class T2, class T3, class T4, class T5>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << endl;
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
       << endl;
}
vector<int> graph[100000 + 7];
int one, two, level[100000 + 7];
bool bfs(int s) {
  queue<int> q;
  int u, v;
  one = 0;
  two = 0;
  q.push(s);
  level[s] = 1;
  one++;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (int i = 0; i < graph[u].size(); i++) {
      v = graph[u][i];
      if (level[v] == 0) {
        if (level[u] == 1) {
          level[v] = 2;
          two++;
        } else {
          level[v] = 1;
          one++;
        }
        q.push(v);
      } else if (level[v] == level[u])
        return true;
    }
  }
  return false;
}
int main() {
  int n, m, u, v, cont = 0;
  long long ans = 0;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &u, &v);
    graph[u].push_back(v);
    graph[v].push_back(u);
    cont = max(cont, (int)graph[u].size());
  }
  if (m == 0) {
    ans = n;
    ans = (1LL * n * (n - 1) * (n - 2)) / 6LL;
    deb(3, ans);
  } else if (cont == 1) {
    ans = 1LL * m * (n - 2);
    deb(2, ans);
  } else {
    for (int i = 1; i <= n; i++) {
      if (level[i] == 0) {
        if (bfs(i)) {
          deb(0, 1);
          return 0;
        }
        if (one) ans += (1LL * one * (one - 1)) / 2LL;
        if (two) ans += (1LL * two * (two - 1)) / 2LL;
      }
    }
    deb(1, ans);
  }
  return 0;
}
