You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

输入格式

第一行包含两个正整数 $N$ 和 $M$，表示有 $N$ 个用户，$M$ 对朋友关系

接下来 $M$ 行，每行描述第 $i$ 对朋友关系。

输出格式

一行一个整数，表示答案。

4 3
1 2
2 3
1 4

3

样例解释 1

三个新的友谊可以如下产生：

1. 用户$1$与用户$3$成为朋友，用户$3$是他们的朋友（用户$2$）的朋友。
2. 用户$3$与用户$4$成为朋友，用户$4$是他们的朋友（用户$1$）的朋友。
3. 用户$2$与用户$4$成为朋友，用户$4$是他们的朋友（用户$1$）的朋友。

不会有四个或更多的新友谊产生。

3 0

0

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

11

数据范围与约定

• 对于 $40\%$ 的数据，$1 \leq N \leq 1000$
• 对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5, 0 \leq M \leq 2 \times 10^5, 1 \leq A_i < B_i \leq N$ 数据保证没有自环。注意，重复的边算一条边。