557_D. Vitaly and Cycle
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 (<image> — 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 ai, bi (1 ≤ ai, bi ≤ 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.
```python
def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def prod(a, mod=10**9+7):
    ans = 1
    for each in a:
        ans = (ans * each) % mod
    return ans

def lcm(a, b): return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

from collections import deque

def bfs(graph, n, alpha, used, color):
    """Breadth first search on a graph!"""
    q = deque([alpha])

    used[alpha] = True
    z, o = 0, 0
    while q:
        v = q.popleft()
        if color[v] == -1:
            color[v] = 0
            z += 1
        for u in graph[v]:
            if not used[u]:
                used[u] = True
                q.append(u)
            if color[u] == color[v]:return False
            if color[u] == -1:
                if color[v] == 1:z+=1
                else: o += 1
            color[u] = (color[v] + 1) % 2
    return (used, color, z, o)

def shortest_path(graph, alpha, omega):
    """Returns the shortest path between two vertices!"""
    used, dist, parents = bfs(graph, alpha)
    if not used[omega]:
        return []
    path = [omega]
    v = omega
    while parents[v] != -1:
        path += [parents[v]]
        v = parents[v]
    return path[::-1]


for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, m = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    #e, f = map(int, input().split())
    graph = [[] for __ in range(n+1)]
    ml = 0
    for i in range(m):
        x, y = map(int, input().split())
        graph[x] += [y]
        graph[y] += [x]
        ml = max(ml, len(graph[x]), len(graph[y]))

    if ml == 0:
        print(3, (n*(n-1)*(n-2))//6)
        continue
    if ml == 1:
        x=0
        for i in graph:
            if len(i) == 1:
                x += 1
        print(2, (x//2)*(n-2))
        continue
    # ans will be 1 if no odd cycle else 0
    cn = connected_components(n+1, graph)
    bipartite = True
    ans = 0
    used = [0]*(n+1)
    color = [-1]*(n+1)
    for i in range(1, len(cn)):
        j = cn[i][0]
        ooff = bfs(graph, n+1, j, used, color)
        if not ooff:
            bipartite = False
            break
        used, color, z, o = ooff
        ans += (z*(z-1)) // 2 + (o*(o-1))//2
    if not bipartite:
        print(0, 1)
        continue

    # ans = 1
    print(1, ans)


```