AT_abc350_d [ABC350D] New Friends

题目描述

有一个 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$
$A_2$ $B_2$
$\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

说明/提示

限制条件

• $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)$ 互不相同
• 输入均为整数

样例解释 1

如下所示，“与朋友的朋友成为新朋友”的操作最多可以进行 $3$ 次。

• 用户 $1$ 与其朋友（用户 $2$）的朋友用户 $3$ 成为新朋友
• 用户 $3$ 与其朋友（用户 $1$）的朋友用户 $4$ 成为新朋友
• 用户 $2$ 与其朋友（用户 $1$）的朋友用户 $4$ 成为新朋友

无法进行第 $4$ 次或更多次操作。

样例解释 2

如果最初不存在任何朋友关系，则无法产生新的朋友关系。

由 ChatGPT 4.1 翻译