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.

题目描述

在—个社交网络中有 N 个用户（编号为 1 到 N），用户之间可以通过朋友关系相连。友谊是双向的：如果 X 是 Y 的朋友，那么 Y 也是 X 的朋友。

目前，网络中有 M 对朋友关系。每对关系由两个用户 Ai 和 Bi 组成。

现在，你可以执行以下操作任意次：

选择三个不同的用户 X, Y, Z，满足：

① X 和 Y 是朋友；② Y 和 Z 是朋友；③ 但 X 和 Z 不是朋友。 然后，让 X 和 Z 成为朋友。

​注意：每次操作后，朋友关系会增加（新增了一条边​），因此后续操作可能基于新的关系进行。

问：最多可以执行多少次这样的操作？

输入格式

第—行包含两个正整数 N 和 M，表示用户数量和现有的朋友关系数量。 接下来 M 行，每行包含两个正整数 Ai 和 Bi，表示—对朋友关系。

输出格式

输出一⾏一个整数，表示最大操作次数。

输入输出样例

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

12

数据范围

对于 40% 的数据， 1 < N ≤ 1000。 对于 100% 的数据， 1 < N ≤ 2 x 10^5 ， 0 < M ≤ 2* 10^5， 1 ≤ Ai < Bi ≤ N，数据保证没有自环。 注意：重复的边算—条边。