#include <bits/stdc++.h>
using namespace std;
const int MAXN = (long long)2e5;
const int INF = (long long)1e9;
const int MOD = (long long)1e9 + 7;
const int CHR = 97;
long long n, m, ans;
bool spec = false;
long long mark[MAXN], cnt[2];
vector<int> g[MAXN];
void Add_Edge(int v, int u) {
  g[v].push_back(u);
  g[u].push_back(v);
}
void bfs(int v) {
  queue<int> Q;
  Q.push(v);
  while (Q.size()) {
    v = Q.front();
    Q.pop();
    for (int i = 0; i < g[v].size(); i++) {
      int u = g[v][i];
      if (!mark[u]) {
        mark[u] = mark[v] + 1;
        Q.push(u);
      }
    }
  }
}
void dfs(int v, int col = 1) {
  mark[v] = col;
  cnt[col - 1]++;
  for (int i = 0; i < g[v].size(); i++) {
    int u = g[v][i];
    if (!mark[u])
      dfs(u, 3 - col);
    else if (mark[v] == mark[u]) {
      spec = true;
      return;
    }
  }
}
void cal(long long x) { ans += x * (x - 1) / 2 * 1LL; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int v, u;
  cin >> n >> m;
  for (int i = 0; i < m; i++) cin >> v >> u, Add_Edge(v, u);
  if (!m) return cout << 3 << " " << n * (n - 1) * (n - 2) / 6 * 1LL << "\n", 0;
  for (int i = 0; i < n; i++)
    if (!mark[i]) {
      cnt[0] = cnt[1] = 0;
      dfs(i);
      cal(cnt[0]), cal(cnt[1]);
      if (spec) return cout << 0 << " " << 1 << "\n", 0;
    }
  if (!ans) return cout << 2 << " " << m * (n - 2) * 1LL << "\n", 0;
  cout << 1 << " " << ans << "\n";
}
