CF557D Vitaly and Cycle

在被大学开除后，Vitaly 开始对图论产生了兴趣。 Vitaly 尤其喜欢长度为奇数、且每个顶点最多只出现一次的环。 Vitaly 想要解决如下问题。给定一个包含 $n$ 个顶点和 $m$ 条边的无向图（图不一定连通，没有重边和自环）。你需要找到 $t$ —— 需要向给定的图中最少添加多少条边，才能形成一个长度大于 $1$ 的简单奇环。此外，你还需要找到 $w$ —— 添加 $t$ 条边，能够形成一个长度大于 $1$ 的奇数简单环的方案数。禁止添加自环或重边。 如果两种加边方案所加的边集合相同，则认为这两种方案是等价的。 由于 Vitaly 不在大学学习，他请你来帮助他解决这个问题。

输入的第一行包含两个整数 $n$ 和 $m$，分别表示图中的顶点数和边数。 接下来的 $m$ 行，每行描述一条边。每条边由一对整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$）组成，表示第 $i$ 条边连接了顶点 $a_i$ 和 $b_i$。每行的各个数字之间用一个空格隔开。 保证给定的图中没有自环和重边。图不一定是连通的。

输出一行，包含两个用空格分隔的整数 $t$ 和 $w$，分别表示需要添加的最少边数，以及形成长度大于 $1$ 的奇数简单环（每个顶点最多出现一次）的方法数。

简单环指的是不包含重复顶点的环。 由 ChatGPT 5 翻译