103503: [Atcoder]ABC350 D - New Friends

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

问题描述

有一个有N个用户使用的社交网络，用户编号从1到N。

在这个社交网络中，两个用户可以成为朋友。友情是双向的；如果用户X是用户Y的朋友，那么用户Y也是用户X的朋友。

目前，社交网络上有M对朋友关系，第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$成为朋友，因为$3$是他们朋友$2$的朋友
• 用户$3$与用户$4$成为朋友，因为$4$是他们朋友$1$的朋友
• 用户$2$与用户$4$成为朋友，因为$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