← 返回题目列表

Codeforces · 557/D

D. 生命和周期

中文机器翻译题面 查看原题

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

Vitaly 特别喜欢奇数长度的循环,其中每个顶点最多出现一次。

Vitaly 想知道如何解决以下问题。给定一个无向图,由 n 个顶点和 m 个边组成,不一定相连,没有平行边和环。您需要找到 t — 为了形成一个奇数长度的简单循环(由多个顶点组成)必须添加到给定图中的最小边数。此外,他必须找到 w——添加 t 条边以形成奇数长度循环(由多个顶点组成)的方法数。禁止添加环路或平行边。

如果向图中添加边的两种方法具有相同的添加边集,则它们被视为相等。

由于维塔利没有在大学学习,他请求你帮助他完成这项任务。

输入

输入的第一行包含两个整数 n 和 m ($$3 \leq n \leq 10^5, 0 \leq m \leq \min\left(\frac{n(n-1)}{2}, 10^5\right)$$ — 图中的顶点数和图中的边数。

接下来的 m 行包含图的边的描述,每行一个边。每条边由一对整数 ai, bi (1 ≤ ai, bi ≤ n) 给出——由第 i 条边连接的顶点。行中的所有数字均由一个空格分隔。

保证给定的图不包含任何循环和平行边。该图不一定是连通的。

输出

在输出的第一行中打印两个空格分隔的整数 t 和 w — 应添加到图中以形成奇数长度的简单循环的最小边数,该循环由多个顶点组成,其中每个顶点最多出现一次,以及执行此操作的方法数。

示例

输入 #1

4 4
1 2
1 3
4 2
4 3

输出 #1

1 2

输入 #2

3 3
1 2
2 3
3 1

输出 #2

0 1

输入 #3

3 0

输出 #3

3 1

注意

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