维塔利被大学开除后,他对图论产生了兴趣。
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
注意
简单循环是两次不包含任何顶点的循环。