D

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

#define INF 1000000000
#define FOR(i, a, b) for(int i=int(a); i<int(b); i++)
#define FORC(cont, it) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define maxN 100000

bool visited[maxN], cyc[maxN];
int visitOrder[maxN];
ii ed[maxN];
vi edges[maxN];

bool findCycles(int n, int v) {
    if (cyc[n]) {
        if ((v - visitOrder[n]) & 1) {
            return true;
        }
        return false;
    }
    if (visited[n]) return false;
    visitOrder[n] = v;
    cyc[n] = true;
    visited[n] = true;
    bool ret = false;
    FOR(i, 0, edges[n].size()) {
        int id = edges[n][i];
        int next = ed[id].second;
        if (ed[id].first != n) next = ed[id].first;
        ret |= findCycles(next, v + 1);
    }
    cyc[n] = false;
    return ret;
}

ll sumN(ll n) {
    return n*(n + 1) / 2;
}

void sum(ii&l, ii r) {
    l.first += r.first;
    l.second += r.second;
}

ii countRB(int n, bool red) {
    ii ret = ii(0, 0);
    if (visited[n]) return ret;
    if (red) ret.first++;
    else ret.second++;
    visited[n] = true;
    FOR(i, 0, edges[n].size()) {
        int id = edges[n][i];
        sum(ret, countRB(ed[id].first, !red));
        sum(ret, countRB(ed[id].second, !red));
    }
    return ret;
}

int main() {
    ll n, m, a, b, minE, ways;
    while (scanf("%I64d %I64d", &n, &m)!=EOF) {
        bool vCount = false;
        FOR(i, 0, n) edges[i].clear();
        FOR(i, 0, m) {
            scanf("%I64d %I64d", &a, &b);
            a--, b--;
            ed[i] = ii(a, b);
            edges[a].push_back(i);
            edges[b].push_back(i);
        }
        memset(visited, false, sizeof(visited));
        bool cycFound = false;
        FOR(i, 0, n) {
            cycFound |= findCycles(i, 0);
            if (edges[i].size() > 1) vCount = true;
        }
        if (cycFound) {
            minE = 0;
            ways = 1;
        }
        else if (vCount) {
            minE = 1;
            ways = 0;
            memset(visited, false, sizeof(visited));
            FOR(i, 0, n) {
                if (edges[i].size()) {
                    ii a = countRB(i, true);
                    ways+=sumN(a.first - 1) + sumN(a.second - 1);
                }
            }
        }
        else if (m) {
            minE = 2;
            ways = m*(n - 2);
        }
        else {
            minE = 3;
            ways = 0;
            FOR(i, 2, n) {
                ways += sumN(i-1);
            }
        }
        printf("%I64d %I64d\n", minE, ways);
    }
    return 0;
}