题目描述

问题陈述

有一个由 $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$，表示该 $N$ 个用户和 $M$ 对朋友关系

接下来 $M$ 行每行包含 2 个整数 $A_i,B_i$，表示 $A_i,B_i$ 是朋友关系

输出格式

输出答案

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), (2, 4), (3, 4)

数据规模与限制

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $A_i \neq B_i$
• $(A_i, B_i) 均不相同, 既没有重边$

来源

• abc_350_D: New Friends