分数: 350 点
问题陈述
有一个 SNS 使用 N 用户,标有来自 1 to N.
在此 SNS 中,两个用户可以成为 朋友 彼此。
友谊是双向的;如果用户 X 是用户 Y 的朋友,则用户 Y 始终是用户 X 的朋友。
目前,有 M SNS 上的友谊,与 i第对由用户组成 A_i 和 B_i.
确定以下操作可以执行的最大次数:
- 操作:选择三个用户X、Y和Z,使得X和Y是朋友,Y和Z是朋友,但X和Z不是朋友。使 X 和 Z 成为朋友。
约束
- 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) 是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 \vdots A_M B_M
输出
打印答案。
示例输入 1
4 3 1 2 2 3 1 4
示例输出 1
3
与朋友的朋友建立三个新的友谊可能如下:
- 用户 1 与用户成为好友 3,谁是他们朋友的朋友(用户 2)
- 用户 3 与用户成为好友 4,谁是他们朋友的朋友(用户 1)
- 用户 2 与用户成为好友 4,谁是他们朋友的朋友(用户 1)
不会有四个或更多的新友谊。
示例输入 2
3 0
示例输出 2
0
如果没有最初的友谊,就不会出现新的友谊。
示例输入 3
10 8 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10
示例输出 3
12