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.
The first line of the input contains two integers *n* and *m* (<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/85eb1262062bdd96de2d3ee9a76a845441ee44af.png" style="max-width: 100.0%;max-height: 100.0%;"/> — 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*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *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.
"""
#If FastIO not needed, use this and don't forget to strip
#import sys, math
#input = sys.stdin.readline
"""

import os
import sys
from io import BytesIO, IOBase
import heapq as h 
from bisect import bisect_left, bisect_right

import time

from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        import os
        self.os = os
        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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
            self.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")

from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

start_time = time.time()

def getInts():
    return [int(s) for s in input().split()]

def getInt():
    return int(input())

def getStrs():
    return [s for s in input().split()]

def getStr():
    return input()

def listStr():
    return list(input())

def getMat(n):
    return [getInts() for _ in range(n)]

MOD = 998244353 
#MOD = 10**9+7

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

"""
Scenarios:
0) no edges, answer is (3,N choose 3)
1) already have an odd cycle: answer is (0,1)
2) no odd cycle, but a connected component of at least size 3: answer is (1,W), where W is the number of paths of length 2
    number of paths of length 2 = sum(x*(x-1)//2) where x is the degree of each vertex
3) no odd cycle, no component of size 3 or more, some isolated edges: answer is (2,M*(N-2))

How to count odd cycles
"""

def solve():
    N, M = getInts()
    #case 0
    if not M:
        print(3,N*(N-1)*(N-2)//6)
        return
    graph = dd(set)
    
    for m in range(M):
        A, B = getInts()
        A -= 1
        B -= 1
        graph[A].add(B)
        graph[B].add(A)

    parent = [-1]*N
    levels = [-1]*N
    
    edges = set()
    
    global flag
    flag = False
    
    @bootstrap
    def dfs(node,level):
        global flag
        levels[node] = level
        visited.add(node)
        nodes.remove(node)
        for neigh in graph[node]:
            if neigh != parent[node] and parent[node] > -1: edges.add((min(parent[node],neigh),max(parent[node],neigh)))
            if neigh in visited and neigh != parent[node] and abs(levels[neigh]-level)%2 == 0:
                flag = True
            if neigh not in visited:
                parent[neigh] = node
                yield dfs(neigh,level+1)
        yield
    
    nodes = set(list(range(N)))
    while nodes:
        node = next(iter(nodes))
        visited = set()
        dfs(node,0)
    
    if flag:
        print(0,1)
        return
    
    #print(edges)
    
    if edges:
        print(1,len(edges))
        return
    
    print(2,M*(N-2))
    return
    
#for _ in range(getInt()):
solve()
    #solve()

#print(time.time()-start_time)