#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000002;
const long long INFLL = 100000000000000000ll;
const long long MOD = 1000000007;
int Color[100005], Par[100005], N, M;
unordered_set<int> E[100005];
vector<int> Verts[100005];
int find(int n) {
  if (Par[n] == n) return n;
  return Par[n] = find(Par[n]);
}
int join(int a, int b) { Par[find(a)] = find(b); }
int main() {
  cin >> N >> M;
  for (int i = (1); i <= (N); i++) Color[i] = -1, Par[i] = i;
  for (int i = (1); i <= (M); i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    E[a].insert(b), E[b].insert(a);
  }
  for (int vert = (1); vert <= (N); vert++)
    if (Color[vert] < 0) {
      Color[vert] = 0;
      queue<int> q;
      q.push(vert);
      while (!q.empty()) {
        int n = q.front();
        q.pop();
        for (int v : E[n]) {
          if (Color[v] == Color[n]) {
            cout << "0 1";
            return 0;
          }
          if (Color[v] < 0) {
            Color[v] = 1 - Color[n];
            q.push(v);
            join(n, v);
          }
        }
      }
    }
  for (int i = (1); i <= (N); i++) {
    int c = find(i);
    Verts[c].push_back(i);
  }
  long long ans = 0;
  for (int c = (1); c <= (N); c++) {
    long long am[2];
    am[0] = am[1] = 0;
    for (int v : Verts[c]) am[Color[v]]++;
    ans += am[0] * (am[0] - 1) / 2;
    ans += am[1] * (am[1] - 1) / 2;
  }
  if (ans > 0)
    cout << "1 " << ans;
  else if (M == 0) {
    cout << "3 ";
    long long n = N;
    ans = n * (n - 1) * (n - 2) / 6ll;
    cout << ans;
  } else {
    cout << "2 ";
    long long m = M;
    long long n = N;
    ans = m * (n - 2);
    cout << ans;
  }
}
