#include <bits/stdc++.h>
using namespace std;
void floodFill(int vertex, int currentComponent,
               const vector<set<int>> &edgeList, vector<int> &component) {
  int N = edgeList.size();
  component[vertex] = currentComponent;
  for (int i : edgeList[vertex]) {
    if (component[i] == -1) {
      floodFill(i, currentComponent, edgeList, component);
    }
  }
}
vector<vector<int>> findComponents(const vector<set<int>> &edgeList) {
  int N = edgeList.size();
  vector<int> component(N, -1);
  vector<vector<int>> componentSets;
  int currentComponent = 0;
  for (int i = 0; i < N; ++i) {
    if (component[i] == -1) {
      componentSets.emplace_back();
      stack<int> s;
      s.push(i);
      component[i] = currentComponent;
      componentSets.back().push_back(i);
      while (!s.empty()) {
        int vertex = s.top();
        s.pop();
        for (int j : edgeList[vertex]) {
          if (component[j] == -1) {
            component[j] = currentComponent;
            componentSets.back().push_back(j);
            s.push(j);
          }
        }
      }
      ++currentComponent;
    }
  }
  return componentSets;
}
bool colorDepthFirst(int vertex, bool color, const vector<set<int>> &edgeList,
                     const unordered_map<int, int> &vertexIdx,
                     vector<bool> &vertexColor, vector<bool> &isColored) {
  int idx = vertexIdx.at(vertex);
  vertexColor[idx] = color;
  isColored[idx] = true;
  for (int i : edgeList[vertex]) {
    int nextIdx = vertexIdx.at(i);
    if (!isColored[nextIdx]) {
      bool isBipartite = colorDepthFirst(i, !color, edgeList, vertexIdx,
                                         vertexColor, isColored);
      if (!isBipartite) return false;
    } else if (vertexColor[nextIdx] == color) {
      return false;
    }
  }
  return true;
}
pair<bool, vector<bool>> getBipartiteColoring(
    const vector<int> &component, const vector<set<int>> &edgeList) {
  unordered_map<int, int> vertexIdx;
  vertexIdx.reserve(component.size());
  for (int i = 0; i < component.size(); ++i) vertexIdx[component[i]] = i;
  vector<bool> vertexColor(component.size());
  vector<bool> isColored(component.size(), false);
  vertexColor[vertexIdx[component.front()]] = true;
  isColored[vertexIdx[component.front()]] = true;
  stack<int> s;
  s.push(component.front());
  while (!s.empty()) {
    int vertex = s.top();
    s.pop();
    int idx = vertexIdx[vertex];
    bool currentColor = vertexColor[idx];
    for (int nextVertex : edgeList[vertex]) {
      int nextIdx = vertexIdx[nextVertex];
      if (!isColored[nextIdx]) {
        vertexColor[nextIdx] = !currentColor;
        isColored[nextIdx] = true;
        s.push(nextVertex);
      } else if (vertexColor[nextIdx] == currentColor) {
        return make_pair(false, vertexColor);
      }
    }
    currentColor = !currentColor;
  }
  return make_pair(true, vertexColor);
}
int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  cin >> N >> M;
  vector<set<int>> edgeList(N);
  for (int m = 0; m < M; ++m) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    edgeList[a].insert(b);
    edgeList[b].insert(a);
  }
  if (M == 0) {
    cout << 3 << ' ' << (((long long)N) * (N - 1) * (N - 2)) / 6 << endl;
    return 0;
  }
  vector<vector<int>> components = findComponents(edgeList);
  int maxComponentSize = 1;
  for (int i = 0; i < components.size(); ++i) {
    if (maxComponentSize < components[i].size())
      maxComponentSize = components[i].size();
  }
  if (maxComponentSize == 2) {
    cout << 2 << ' ' << ((long long)M) * (N - 2) << endl;
    return 0;
  } else {
    long long waysToMakeOddCycle = 0;
    for (int i = 0; i < components.size(); ++i) {
      bool isBipartite;
      vector<bool> bipartiteColoring;
      tie(isBipartite, bipartiteColoring) =
          getBipartiteColoring(components[i], edgeList);
      if (!isBipartite) {
        cout << '0' << ' ' << 1 << endl;
        return 0;
      } else {
        int setASize = 0;
        int setBSize = 0;
        for (bool color : bipartiteColoring) {
          if (color) {
            ++setASize;
          } else {
            ++setBSize;
          }
        }
        waysToMakeOddCycle += ((long long)setASize) * (setASize - 1) / 2 +
                              ((long long)setBSize) * (setBSize - 1) / 2;
      }
    }
    cout << 1 << ' ' << waysToMakeOddCycle << endl;
    return 0;
  }
}
