新朋友

题目描述

有一个 SNS,由 $N$ 位用户使用,编号为 $1$ 到 $N$。

在这个 SNS 中,两位用户可以互相成为朋友。

朋友关系是双向的:如果用户 X 是用户 Y 的朋友,那么用户 Y 也总是用户 X 的朋友。

目前,SNS 上有 $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

可以通过「朋友的朋友」产生三对新朋友,如下所示:

• 用户 $1$ 与用户 $3$ 成为朋友,其中用户 $3$ 是用户 $1$ 的朋友(用户 $2$)的朋友。
• 用户 $3$ 与用户 $4$ 成为朋友,其中用户 $4$ 是用户 $3$ 的朋友(用户 $1$)的朋友。
• 用户 $2$ 与用户 $4$ 成为朋友,其中用户 $4$ 是用户 $2$ 的朋友(用户 $1$)的朋友。

不会产生四对或更多的新朋友。

3 0

0

如果没有任何初始朋友关系,就不会产生新朋友。

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

12

数据范围

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