题目描述

Rng有一个有 $N$ 个顶点的连通无向图。目前图中有 $M$ 条边，第 $i$ 条边连接了顶点 $A_i$ 和 $B_i$。

Rng将通过重复以下操作向图中添加新边：

• 操作：选择 $u$ 和 $v$ $(u \\neq v)$，使得从顶点 $u$ 出发经过正好三条边可以到达顶点 $v$，然后添加一条连接顶点 $u$ 和 $v$ 的边。如果顶点 $u$ 和 $v$ 之间已经存在一条边，则不允许再次添加边。

找到能够添加的最大可能边数。

约束条件

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i,B_i \leq N$
• 图中没有自环或重复的边。
• 图是连通的。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$

输出

找到能够添加的最大可能边数。

示例输入1

6 5
1 2
2 3
3 4
4 5
5 6

示例输出1

4

如果按照下面所示的方式添加边，最多可以添加四条边。

示例输入2

5 5
1 2
2 3
3 1
5 4
5 1

示例输出2

5

例如，可以添加五条边如下：

• 添加一条连接顶点 $5$ 和顶点 $3$ 的边。
• 添加一条连接顶点 $5$ 和顶点 $2$ 的边。
• 添加一条连接顶点 $4$ 和顶点 $1$ 的边。
• 添加一条连接顶点 $4$ 和顶点 $2$ 的边。
• 添加一条连接顶点 $4$ 和顶点 $3$ 的边。