#include <bits/stdc++.h>
using namespace std;
const long long MAX_N = 100005;
vector<long long> cC[MAX_N];
bool finalCheck = false;
bool vis[MAX_N] = {0};
long long tV[MAX_N] = {0};
long long dC[MAX_N][2];
vector<long long> adj[MAX_N];
long long n, m;
void dfs(long long x, long long count, long long t) {
  cC[count].push_back(x);
  vis[x] = 1;
  dC[count][t]++;
  tV[x] = t;
  for (int i = 0; i < adj[x].size(); i++)
    if (!vis[adj[x][i]])
      dfs(adj[x][i], count, 1 - t);
    else if (tV[adj[x][i]] == tV[x]) {
      finalCheck = true;
    }
}
void process() {
  long long count = 0, count_3 = 0;
  ;
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      count++;
      dC[count][0] = dC[count][1] = 0;
      dfs(i, count, 0);
      count_3 += dC[count][0] * (dC[count][0] - 1) / 2 +
                 dC[count][1] * (dC[count][1] - 1) / 2;
    }
  if (finalCheck)
    cout << "0 1" << endl;
  else {
    if (count_3 > 0)
      cout << 1 << " " << count_3 << endl;
    else
      cout << 2 << " " << m * (n - 2) << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  int u, v;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  if (m == 0) {
    cout << 3 << " " << n * (n - 1) * (n - 2) / 6 << endl;
  } else
    process();
  return 0;
}
