题目描述

有一个由$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$

输出格式

输出所求答案。

样例

4 3
1 2
2 3
1 4

3

3 0

0

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

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)$对是互不相同的。
• 所有输入值都是整数。

来源

• AtCoder ABC350D