CF557D.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.

维塔利被大学开除后，开始对图论产生了兴趣。

维塔利尤其喜欢长度为奇数的简单环（即每个顶点至多出现一次）。

维塔利一直在思考如下问题：给定一个包含 $n$ 个顶点和 $m$ 条边的无向图（该图未必连通，且不含重边和自环）。你需要求出 $t$ —— 使得原图中存在一个顶点数大于一的奇长简单环所需添加的最少边数。此外，还需计算 $w$ —— 在恰好添加 $t$ 条边的前提下，能够形成一个顶点数大于一的奇长简单环的方案总数。注意：禁止添加自环或重边。

若两种加边方案所添加的边集完全相同，则视为同一种方案。

由于维塔利已不在大学就读，他请你帮忙解决这一问题。

The first line of the input contains two integers n and m ( — 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.

输入的第一行包含两个整数 $n$ 和 $m$（ — 图中顶点的数量和边的数量）。

接下来的 $m$ 行描述图中的边，每行描述一条边。每条边由一对整数 $a_i$, $b_i$（$1 \le a_i, b_i \le n$）给出 —— 表示第 $i$ 条边所连接的两个顶点。每行中的所有数字均以单个空格分隔。

保证所给图中不含任何自环（loop）和平行边（parallel edge）。该图不一定是连通的。

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.

在输出的第一行中，打印两个用空格分隔的整数 $t$ 和 $w$ —— 分别表示为使图中形成一个长度为奇数的简单环（该环包含多于一个顶点，且每个顶点至多出现一次）所需添加的最少边数，以及实现该目标的方法数。

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

简单环是指不包含任何顶点两次的环。