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: HARD
Tags: Graph algorithms

Graph traversal

Combinatorics

Mathematics

Starter code:

Solutions:
(n, m) = [int(x) for x in input().split()]
E = {i: [] for i in range(n)}
for i in range(m):
	(u, v) = [int(x) - 1 for x in input().split()]
	E[v].append(u)
	E[u].append(v)

def dfs():
	visited = [False for i in range(n)]
	colour = [0 for i in range(n)]
	ans = 0
	for v in range(n):
		if visited[v]:
			continue
		stack = [(v, 0)]
		part = [0, 0]
		while stack:
			(node, c) = stack.pop()
			if not visited[node]:
				part[c] += 1
				visited[node] = True
				colour[node] = c
				stack.extend(((u, c ^ 1) for u in E[node]))
			elif c != colour[node]:
				return (0, 1)
		ans += (part[0] * (part[0] - 1) + part[1] * (part[1] - 1)) // 2
	return (1, ans)
if m == 0:
	print(3, n * (n - 1) * (n - 2) // 6)
elif max((len(E[v]) for v in E)) == 1:
	print(2, m * (n - 2))
else:
	ans = dfs()
	print(ans[0], ans[1])


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
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')
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):
	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):
	(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, m) = 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
	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
	print(1, ans)


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()


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

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

def solve():
	(N, M) = getInts()
	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
		global odds
		global evens
		levels[node] = level
		if level:
			odds += 1
		else:
			evens += 1
		visited.add(node)
		nodes.remove(node)
		for neigh in graph[node]:
			if neigh in visited and neigh != parent[node] and (levels[neigh] == level):
				flag = True
			if neigh not in visited:
				parent[neigh] = node
				yield dfs(neigh, level ^ 1)
		yield
	ans = 0
	nodes = set(list(range(N)))
	while nodes:
		node = next(iter(nodes))
		visited = set()
		global odds
		odds = 0
		global evens
		evens = 0
		dfs(node, 0)
		ans += odds * (odds - 1) // 2 + evens * (evens - 1) // 2
	if flag:
		print(0, 1)
		return
	if ans:
		print(1, ans)
		return
	if edges:
		print(1, len(edges))
		return
	print(2, M * (N - 2))
	return
solve()


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)


import sys
import threading
threading.stack_size(67108864)
sys.setrecursionlimit(100500)

def nc2(k):
	return k * (k - 1) // 2

def solve():

	def dfs(u):
		comp[u] = n_comp
		for v in g[u]:
			if color[v] == 0:
				color[v] = 3 - color[u]
				dfs(v)
			elif color[u] == color[v]:
				return True
		return False

	def check(g, color, n):
		for v in range(1, n + 1):
			for u in g[v]:
				if color[u] == color[v]:
					return False
		return True
	(n, m) = map(int, input().split())
	g = dict()
	for i in range(1, n + 1):
		g[i] = set()
	for i in range(m):
		(a, b) = map(int, input().split())
		g[a].add(b)
		g[b].add(a)
	color = [0] * (n + 1)
	comp = [0] * (n + 1)
	n_comp = 0
	for u in range(1, n + 1):
		if color[u] == 0:
			n_comp += 1
			color[u] = 1
			if dfs(u):
				print(0, 1)
				return
	if not check(g, color, n):
		print(0, 1)
		return
	counts = [0] * (n_comp + 1)
	counts_1 = [0] * (n_comp + 1)
	counts_2 = [0] * (n_comp + 1)
	for i in range(1, n + 1):
		counts[comp[i]] += 1
		if color[i] == 1:
			counts_1[comp[i]] += 1
		else:
			counts_2[comp[i]] += 1
	c = max(counts)
	if c == 1:
		print(3, n * (n - 1) * (n - 2) // 6)
	elif c == 2:
		print(2, m * (n - 2))
	elif c >= 3:
		ans = 0
		for i in range(1, n_comp + 1):
			if counts[i] >= 3:
				ans += nc2(counts_1[i]) + nc2(counts_2[i])
		print(1, ans)
thread = threading.Thread(target=solve)
thread.start()