[ABC350] D - New Friends

D - New Friends

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 350 分

题面

有一个标记为从 到 的 个用户使用的 SNS。

在这个 SNS 中，两个用户可以互相成为朋友。
友谊是双向的；如果用户 X 是用户 Y 的朋友，则用户 Y 总是用户 X 的朋友。

当前，在 SNS 上有 对朋友关系，第 对由用户 和 组成。

确定可以执行以下操作的最大次数：

• 操作: 选择三个用户 X、Y 和 Z，使得 X 和 Y 是朋友，Y 和 Z 是朋友，但 X 和 Z 不是朋友。使 X 和 Z 成为朋友。

限制条件

• 所有输入值均为整数。

---

输入

输入以以下格式从标准输入给出：

输出

输出答案。

---

输入样例 1

4 3
1 2
2 3
1 4

输出样例 1

3

可以执行三次朋友的朋友关系操作，如下所示：

• 用户 与用户 成为朋友，用户 是他们的朋友（用户 ）的朋友
• 用户 与用户 成为朋友，用户 是他们的朋友（用户 ）的朋友
• 用户 与用户 成为朋友，用户 是他们的朋友（用户 ）的朋友

不会有四个或更多的新朋友关系。

---

输入样例 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