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$

请输出答案。

## 限制条件 - $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 翻译