AT_code_festival_2017_qualb_c 3 Steps

りんごさん有一个包含 $N$ 个顶点的连通无向图。在这个图中已经存在 $M$ 条边，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。 りんごさん打算通过以下操作向图中添加边： - 操作：选择一对满足 $u \neq v$ 的顶点 $u$ 和 $v$，使得从顶点 $u$ 出发恰好经过 $3$ 条边可以到达顶点 $v$，并在顶点 $u$ 和顶点 $v$ 之间添加一条边。如果顶点 $u$ 和顶点 $v$ 之间已经有边，则不能再添加这条边。 请你计算りんごさん最多可以添加多少条边。

输入以以下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_M$ $B_M$

输出可以添加的边的最大数量。

## 限制条件 - $2 \leq N \leq 10^5$ - $1 \leq M \leq 10^5$ - $1 \leq A_i, B_i \leq N$ - 不存在重边和自环 - 给出的图保证是连通的 ## 样例说明 1 如下图，可以添加 $4$ 条边，无法再继续添加边。  ## 样例说明 2 例如，按照如下顺序添加边，则可以添加 $5$ 条边。 - 在顶点 $5$ 与顶点 $3$ 之间添加一条边。 - 在顶点 $5$ 与顶点 $2$ 之间添加一条边。 - 在顶点 $4$ 与顶点 $1$ 之间添加一条边。 - 在顶点 $4$ 与顶点 $2$ 之间添加一条边。 - 在顶点 $4$ 与顶点 $3$ 之间添加一条边。 由 ChatGPT 5 翻译