该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

有一个由 $N$ 个用户使用的 GTQchat，用从 $1$ 到 $N$ 的数字标记。

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

当前，在 GTQchat 上存在 $M$ 对友谊，其中第 $i$ 对由用户 $A_i$ 和 $B_i$ 组成。

求出可执行以下操作的最大次数:

• 选择三个用户 $X$、$Y$ 和 $Z$，满足： $X$ 和 $Y$ 是朋友，$Y$ 和 $Z$ 是朋友，但 $X$ 和 $Z$ 不是朋友。让 $X$ 和 $Z$ 成为朋友。

数据规模

$2\leq N\leq 2×10^5$

$0\leq M\leq 2×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$

输出

打印答案。

4 3
1 2
2 3
1 4

3

与朋友的朋友建立的三种新友谊如下:

• 用户 1 与用户 3 成为朋友，他们的共同朋友是 2。
• 用户 3 与用户 4 成为朋友，他们的共同朋友是 1。
• 用户 2 与用户 4 成为朋友，他们的共同朋友是 1。

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

3 0

0

如果没有最初的友谊，就不会有新的友谊。

10 8
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10

12