After Vitaly was expelled from the university, he became interested in the graph theory.

Vitaly especially liked the cycles of an odd length in which each vertex occurs at most once.

Vitaly was wondering how to solve the following problem. You are given an undirected graph consisting of n vertices and m edges, not necessarily connected, without parallel edges and loops. You need to find t — the minimum number of edges that must be added to the given graph in order to form a simple cycle of an odd length, consisting of more than one vertex. Moreover, he must find w — the number of ways to add t edges in order to form a cycle of an odd length (consisting of more than one vertex). It is prohibited to add loops or parallel edges.

Two ways to add edges to the graph are considered equal if they have the same sets of added edges.

Since Vitaly does not study at the university, he asked you to help him with this task.


-----Input-----

The first line of the input contains two integers n and m ($3 \leq n \leq 10^{5}, 0 \leq m \leq \operatorname{min}(\frac{n(n - 1)}{2}, 10^{5})$ — the number of vertices in the graph and the number of edges in the graph.

Next m lines contain the descriptions of the edges of the graph, one edge per line. Each edge is given by a pair of integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n) — the vertices that are connected by the i-th edge. All numbers in the lines are separated by a single space.

It is guaranteed that the given graph doesn't contain any loops and parallel edges. The graph isn't necessarily connected.


-----Output-----

Print in the first line of the output two space-separated integers t and w — the minimum number of edges that should be added to the graph to form a simple cycle of an odd length consisting of more than one vertex where each vertex occurs at most once, and the number of ways to do this.


-----Examples-----
Input
4 4
1 2
1 3
4 2
4 3

Output
1 2

Input
3 3
1 2
2 3
3 1

Output
0 1

Input
3 0

Output
3 1



-----Note-----

The simple cycle is a cycle that doesn't contain any vertex twice.

Difficulty: interview

Starter code:

Solutions:
def read_data():
    n, m = list(map(int, input().split()))
    Es = [[] for v in range(n)]
    for e in range(m):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        Es[a].append(b)
        Es[b].append(a)
    return n, m, Es

def solve(n, m, Es):
    if m == 0:
        return 3, n * (n - 1) * (n - 2) // 6
    if max(list(map(len, Es))) == 1:
        return 2, m * (n-2)
    patterns = 0
    color = [0] * n
    for u in range(n):
        if color[u]:
            continue
        color[u] = 1
        stack = [u]
        n_color = [1, 0]
        while stack:
            v = stack.pop()
            prev_color = color[v]
            for w in Es[v]:
                current_color = color[w]
                if current_color == prev_color:
                    return 0, 1
                if current_color == 0:
                    color[w] = - prev_color
                    n_color[(prev_color + 1)//2] += 1
                    stack.append(w)
        n_even = n_color[0]
        n_odd = n_color[1]
        patterns += n_even * (n_even - 1) // 2 + n_odd * (n_odd - 1) // 2
    return 1, patterns

def __starting_point():
    n, m, Es = read_data()
    print(*solve(n, m, Es))

__starting_point()

g = [[] for _ in range(100005)]

n, m = list(map(int, input().split(' ')))
for i in range(m):
    a, b = list(map(int, input().split(' ')))
    g[a].append(b)
    g[b].append(a)

colour = [0] * 100005
v = [0] * 100005

cycle = False
two = True
twos = 0
ones = 0
ans = 0 
for i in range(1, n+1):
    cs = 0
    c1 = 0
    c2 = 0
    if (not colour[i]):
        q = [i]
        colour[i] = 1
        while q:
            cs += 1
            top = q.pop()
            if colour[top] == 1:
                c1 += 1
            else: c2 += 1
            for j in g[top]:    
                if colour[j] == colour[top]:
                    cycle = True
                elif colour[j] == 0:
                    colour[j] = -colour[top]
                    q = [j] + q
        if cs > 2:
            two = False
            ans += ((c1*(c1-1))//2 + (c2*(c2-1))//2)
        if cs == 2:
            twos += 1
            
        if cs == 1:
            ones += 1
if cycle:
    print(0, 1)
    quit()

if m == 0:
    print(3, (n*(n-1)*(n-2)//6))
    quit()
if two:
    print(2, twos*ones + 4 * (twos * (twos - 1) // 2))
    quit()
sumx = 0
for i in range(1, n+1):
    ll = len(g[i])
    sumx += ll * (ll-1) // 2
print(1, ans)


# 解説AC
# 二部グラフでないグラフの性質や，パスの長さを考察する

def main():
    N, M = (int(i) for i in input().split())

    par = [i for i in range(N)]
    size = [1 for i in range(N)]

    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            size[x] = size[par[x]]
            return par[x]

    def same(x, y):
        return find(x) == find(y)

    def union(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if size[x] < size[y]:
            x, y = y, x
        size[x] += size[y]
        par[y] = x

    def get_size(x):
        return size[find(x)]

    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        union(a-1, b-1)

    S = [False]*4
    for i in range(N):
        S[min(3, get_size(i))] = True
        if S[3]:
            break
    t = 0
    if S[3]:
        t = 1
    elif S[2]:
        t = 2
    else:
        t = 3

    color = [-1]*N

    def dfs(s):
        stack = [s]
        color[s] = 0
        b = 1
        w = 0
        while stack:
            v = stack.pop()
            for u in G[v]:
                if color[u] != -1:
                    if color[u] == color[v]:
                        return False, b*w
                    continue
                color[u] = color[v] ^ 1
                if color[u] == 0:
                    b += 1
                else:
                    w += 1
                stack.append(u)
        return True, b*(b-1)//2 + w*(w-1)//2

    is_bipartite, _ = dfs(0)
    if is_bipartite:
        w = 0
        if t == 3:
            w = N*(N-1)*(N-2)//3//2
        elif t == 2:
            used = [False]*N
            for i in range(N):
                if not used[find(i)] and get_size(i) == 2:
                    w += (N-2)
                    used[find(i)] = True
        elif t == 1:
            used = [False]*N
            color = [-1]*N
            for i in range(N):
                if not used[find(i)] and get_size(i) >= 3:
                    _, ways = dfs(i)
                    w += ways
                    used[find(i)] = True
        print(t, w)
    else:
        print(0, 1)


def __starting_point():
    main()

__starting_point()

def main():
    N, M = (int(i) for i in input().split())

    par = [i for i in range(N)]
    size = [1 for i in range(N)]

    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            size[x] = size[par[x]]
            return par[x]

    def same(x, y):
        return find(x) == find(y)

    def union(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if size[x] < size[y]:
            x, y = y, x
        size[x] += size[y]
        par[y] = x

    def get_size(x):
        return size[find(x)]

    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        union(a-1, b-1)

    S = [False]*4
    for i in range(N):
        S[min(3, get_size(i))] = True
        if S[3]:
            break
    t = 0
    if S[3]:
        t = 1
    elif S[2]:
        t = 2
    else:
        t = 3

    color = [-1]*N

    def dfs(s):
        stack = [s]
        color[s] = 0
        b = 1
        w = 0
        while stack:
            v = stack.pop()
            for u in G[v]:
                if color[u] != -1:
                    if color[u] == color[v]:
                        return False, b*w
                    continue
                color[u] = color[v] ^ 1
                if color[u] == 0:
                    b += 1
                else:
                    w += 1
                stack.append(u)
        return True, b*(b-1)//2 + w*(w-1)//2

    is_bipartite, _ = dfs(0)
    if is_bipartite:
        w = 0
        if t == 3:
            w = N*(N-1)*(N-2)//3//2
        elif t == 2:
            used = [False]*N
            for i in range(N):
                if not used[find(i)] and get_size(i) == 2:
                    w += (N-2)
                    used[find(i)] = True
        elif t == 1:
            used = [False]*N
            color = [-1]*N
            for i in range(N):
                if not used[find(i)] and get_size(i) >= 3:
                    _, ways = dfs(i)
                    w += ways
                    used[find(i)] = True
        print(t, w)
    else:
        print(0, 1)


def __starting_point():
    main()

__starting_point()

def main():
    N, M = (int(i) for i in input().split())
 
    par = [i for i in range(N)]
    size = [1 for i in range(N)]
 
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            size[x] = size[par[x]]
            return par[x]
 
    def same(x, y):
        return find(x) == find(y)
 
    def union(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if size[x] < size[y]:
            x, y = y, x
        size[x] += size[y]
        par[y] = x
 
    def get_size(x):
        return size[find(x)]
 
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        union(a-1, b-1)
 
    S = [False]*4
    for i in range(N):
        S[min(3, get_size(i))] = True
        if S[3]:
            break
    t = 0
    if S[3]:
        t = 1
    elif S[2]:
        t = 2
    else:
        t = 3
 
    color = [-1]*N
 
    def dfs(s):
        stack = [s]
        color[s] = 0
        b = 1
        w = 0
        while stack:
            v = stack.pop()
            for u in G[v]:
                if color[u] != -1:
                    if color[u] == color[v]:
                        return False, b*w
                    continue
                color[u] = color[v] ^ 1
                if color[u] == 0:
                    b += 1
                else:
                    w += 1
                stack.append(u)
        return True, b*(b-1)//2 + w*(w-1)//2
 
    is_bipartite, _ = dfs(0)
    if is_bipartite:
        w = 0
        if t == 3:
            w = N*(N-1)*(N-2)//3//2
        elif t == 2:
            used = [False]*N
            for i in range(N):
                if not used[find(i)] and get_size(i) == 2:
                    w += (N-2)
                    used[find(i)] = True
        elif t == 1:
            used = [False]*N
            color = [-1]*N
            for i in range(N):
                if not used[find(i)] and get_size(i) >= 3:
                    _, ways = dfs(i)
                    w += ways
                    used[find(i)] = True
        print(t, w)
    else:
        print(0, 1)
 
 
def __starting_point():
    main()

__starting_point()