Score: $350$ points

问题陈述

有一个社交网络服务（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 成为朋友。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is an SNS used by $N$ users, labeled with numbers from $1$ to $N$.

In this SNS, two users can become friends with each other.
Friendship is bidirectional; if user X is a friend of user Y, user Y is always a friend of user X.

Currently, there are $M$ pairs of friendships on the SNS, with the $i$-th pair consisting of users $A_i$ and $B_i$.

Determine the maximum number of times the following operation can be performed:

• Operation: Choose three users X, Y, and Z such that X and Y are friends, Y and Z are friends, but X and Z are not. Make X and Z friends.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq N$
• The pairs $(A_i, B_i)$ are distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

Output

Print the answer.

Sample Input 1

4 3
1 2
2 3
1 4

Sample Output 1

3

Three new friendships with a friend's friend can occur as follows:

• User $1$ becomes friends with user $3$, who is a friend of their friend (user $2$)
• User $3$ becomes friends with user $4$, who is a friend of their friend (user $1$)
• User $2$ becomes friends with user $4$, who is a friend of their friend (user $1$)

There will not be four or more new friendships.

Sample Input 2

3 0

Sample Output 2

0

If there are no initial friendships, no new friendships can occur.

Sample Input 3

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

Sample Output 3

12