题目描述

有一个由 $N$个用户使用的社交网络,用户编号从$1$ 到 $N$ 。在这个社交网络中,两个用户可以成为"朋友"。朋友关系是双向的;如果用户 $X$ 是用户 $Y$ 的朋友,那么用户 $Y$ 也一定是用户 $X$的朋友。

目前,社交网络上有 $M$ 对朋友关系,第i对朋友关系由用户 $A_i$ 和 $B_i$ 组成。

请确定以下操作最多可以执行多少次:

• 操作:选择三个用户 $X$、$Y$ 和 $Z$ ,使得 $X$ 和 $Y$ 是朋友, $Y$和 $Z$是朋友, 但 $X$ 和 $Z$不是朋友。然后让 $X$和 $Z$ 成为朋友。

输入格式

输入从标准输入中以下列格式给出:

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

4 3
1 2
2 3
1 4

输出 #1

3

输入输出样例 #2

输入 #2

3 0

输出 #2

0

输入输出样例 #3

输入 #3

10 8
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10

输出 #3

12

说明/提示

样例 1 解释

可以发生三次新的朋友关系,如下:

用户1与用户3成为朋友,3是1的朋友(用户2)的朋友

用户3与用户4成为朋友,4是3的朋友(用户1)的朋友

用户2与用户4成为朋友,4是2的朋友(用户1)的朋友

不可能有四次或更多的新朋友关系。

样例 2 解释

如果最初没有朋友关系,就不可能产生新的朋友关系。

数据范围

• $2\ \leq\ N\ \leq\ 2\times\ 10^5$
• $0\ \leq\ M\ \leq\ 2\times\ 10^5$
• $1\leq\ A_i\ <\ B_i\ \leq\ N$
• $(A_i,B_i)$ 对是互不相同的。
• 所有输入值都是整数。