← 返回题目列表

AtCoder · abc350_d

G. 新朋友

中文机器翻译题面 查看原题

分数: 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